Ви переглядаєте онлайн-колекцію з $n$ предметів, пронумерованих від $1$ до $n$ та розташованих по колу. Праворуч від кожного предмета $i$ розташований предмет $i+1$, а праворуч від предмета $n$ — предмет $1$. Аналогічно, ліворуч від кожного предмета $i$ розташований предмет $i-1$, а ліворуч від предмета $1$ — предмет $n$.

Предмети мають $m$ параметрів, пронумерованих від $1$ до $m$. Значення параметра $j$ предмета $i$ — ціле число $a_{i,j}$.

Під час перегляду в кожен момент вказівник спрямований на певний предмет, який називається поточним.

Крім того, ви можете керувати множиною умов фільтрації. Кожна умова — це пара $(j,v)$, яка означає, що $j$-й параметр предмета має дорівнювати $v$. Поточний предмет завжди задовольняє всі умови множини.

Для перегляду колекції можна виконувати операції. Кожна операція має бути одного з таких чотирьох видів:

• Натиснути «праворуч». Вказівник переміщується на найближчий праворуч від поточного предмет, що задовольняє всі умови фільтрації. Зокрема, якщо поточний предмет є єдиним таким предметом, вказівник не рухається.

• Натиснути «ліворуч». Аналогічно, вказівник переміщується на найближчий ліворуч від поточного предмет, що задовольняє всі умови фільтрації, і залишається на місці, якщо поточний предмет є єдиним таким предметом.

• Додати нову умову фільтрації $(j,v)$ для деяких цілих чисел $j$ та $v$. Якщо поточний предмет задовольняє цю умову, вказівник не рухається. Інакше він переміщується на найближчий праворуч від поточного предмет, що задовольняє всі умови фільтрації, включно з новою. Якщо такого предмета немає, операція недопустима й не може бути виконана.

• Видалити з множини будь-яку умову фільтрації $(j,v)$. Вказівник не рухається.

Для кожної впорядкованої пари предметів $(i,j)$ дайте відповідь на таке запитання:

• Якщо розпочати перегляд із вказівником на предметі $i$ та порожньою множиною умов фільтрації, яка найменша кількість операцій потрібна, щоб перемістити вказівник на предмет $j$? Наприкінці множина умов фільтрації може бути довільною.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ — кількість предметів у колекції та кількість параметрів кожного предмета ($2\le n\le500$; $1\le m\le5$).

$i$-й з наступних $n$ рядків містить $m$ цілих чисел $a_{i,1},a_{i,2},\ldots,a_{i,m}$ — значення параметрів предмета $i$ ($1\le a_{i,j}\le n$).

Вихідні дані

Виведіть $n$ рядків по $n$ цілих чисел у кожному.

$j$-те число в $i$-му рядку має дорівнювати найменшій кількості операцій, потрібних для переміщення вказівника з предмета $i$ на предмет $j$, починаючи з порожньої множини умов фільтрації.

Приклади

Вхідні дані 1

9 3
5 3 7
5 3 4
5 3 7
5 3 2
5 3 4
5 3 7
2 3 7
5 3 7
2 3 7

Вихідні дані 1

0 1 2 1 2 3 1 2 1
1 0 1 1 2 2 1 3 2
2 1 0 1 1 2 1 3 2
3 2 1 0 1 1 1 3 2
3 2 2 1 0 1 1 3 2
3 1 2 1 1 0 1 2 2
2 1 3 1 2 1 0 1 2
2 1 3 1 2 2 1 0 1
1 1 3 1 2 3 2 1 0

Примітка

У прикладі один із найшвидших способів перейти з предмета 2 на предмет 5 такий:

• Додати нову умову фільтрації $(3,4)$. Оскільки параметр 3 предмета 2 справді дорівнює 4, вказівник залишається на предметі 2.

• Натиснути «праворуч». Вказівник переміщується на найближчий праворуч від предмета 2 предмет, що задовольняє єдину чинну умову $(3,4)$. Це предмет 5. (Натомість можна також натиснути «ліворуч».)

Один із найшвидших способів перейти з предмета 8 на предмет 3 такий:

• Додати нову умову фільтрації $(3,4)$. Оскільки предмет 8 не задовольняє цю умову, вказівник переміщується на найближчий праворуч від предмета 8 предмет, у якого параметр 3 дорівнює 4. Це предмет 2.

• Видалити умову фільтрації $(3,4)$. Вказівник залишається на предметі 2.

• Натиснути «праворуч». Оскільки в множині немає умов фільтрації, вказівник переміщується на предмет 3.