Вы просматриваете онлайн-коллекцию из $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.