컬렉션 둘러보기

온라인 컬렉션에 항목 $n$개가 원형으로 놓여 있고, 항목에는 1번부터 $n$번까지 번호가 붙어 있다. 항목 $i$의 오른쪽 항목은 $i + 1$이고, 항목 $n$의 오른쪽 항목은 1이다. 마찬가지로 항목 $i$의 왼쪽 항목은 $i - 1$이고, 항목 1의 왼쪽 항목은 $n$이다.

항목에는 1번부터 $m$번까지 번호가 붙은 $m$개의 매개변수가 있다. 항목 $i$의 $j$번째 매개변수 값은 정수 $a_{i, j}$이다.

둘러보는 동안 포인터는 항상 어떤 항목을 가리키며, 이 항목을 현재 항목이라고 한다. 또한 필터 조건의 집합을 관리할 수 있다. 각 조건은 $(j, v)$의 쌍이며, 항목의 $j$번째 매개변수 값이 $v$와 같아야 한다는 뜻이다. 현재 항목은 집합의 모든 조건을 항상 만족한다.

컬렉션을 둘러보려면 연산을 수행한다. 연산은 다음 네 가지 중 하나여야 한다.

• 오른쪽 클릭. 포인터는 현재 항목의 오른쪽에 있으면서 모든 필터 조건을 만족하는 가장 가까운 항목으로 이동한다. 현재 항목이 그런 항목 중 유일하면 포인터는 움직이지 않는다.
• 왼쪽 클릭. 포인터는 현재 항목의 왼쪽에 있으면서 모든 필터 조건을 만족하는 가장 가까운 항목으로 이동한다. 현재 항목이 그런 항목 중 유일하면 포인터는 움직이지 않는다.
• 새 필터 조건 $(j, v)$ 추가. 현재 항목이 이 조건을 만족하면 포인터는 움직이지 않는다. 만족하지 않으면, 새 조건을 포함한 모든 필터 조건을 만족하는 항목 중 현재 항목의 오른쪽에서 가장 가까운 항목으로 포인터가 이동한다. 그런 항목이 없으면 이 연산은 불법이므로 수행할 수 없다.
• 필터 조건 $(j, v)$ 중 하나를 제거. 포인터는 움직이지 않는다.

모든 순서쌍 $(i, j)$에 대해 다음 질문에 답하라. 항목 $i$에 포인터를 두고 필터 조건 집합이 비어 있는 상태에서 둘러보기를 시작할 때, 포인터를 항목 $j$로 옮기는 데 필요한 연산의 최소 횟수는 얼마인가? 필터 조건 집합은 마지막에 어떤 상태여도 된다.

첫 줄에 항목 수 $n$과 항목당 매개변수 수 $m$이 주어진다 ($2 \le n \le 500$; $1 \le m \le 5$).

다음 $n$개 줄의 $i$번째 줄에는 항목 $i$의 매개변수 값 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$이 주어진다 ($1 \le a_{i, j} \le n$).

$n$개 줄을 출력한다. $i$번째 줄의 $j$번째 정수는 필터 조건 집합이 비어 있는 상태에서 항목 $i$로부터 항목 $j$로 포인터를 옮기는 데 필요한 최소 연산 횟수이다.

예제 테스트에서 항목 $2$에서 항목 $5$로 가는 가장 빠른 방법 중 하나는 다음과 같다.

• 필터 조건 $(3, 4)$를 추가한다. 항목 $2$의 3번째 매개변수 값이 4이므로 포인터는 항목 $2$에 머문다.
• 오른쪽 클릭한다. 활성 조건 $(3, 4)$를 만족하는 항목 중 항목 $2$의 오른쪽에서 가장 가까운 항목으로 이동하며, 그 항목은 항목 $5$이다. (왼쪽 클릭해도 된다.)

항목 $8$에서 항목 $3$으로 가는 가장 빠른 방법 중 하나는 다음과 같다.

• 필터 조건 $(3, 4)$를 추가한다. 항목 $8$은 이 조건을 만족하지 않으므로, 3번째 매개변수 값이 4인 항목 중 항목 $8$의 오른쪽에서 가장 가까운 항목인 항목 $2$로 이동한다.
• 필터 조건 $(3, 4)$를 제거한다. 포인터는 항목 $2$에 머문다.
• 오른쪽 클릭한다. 필터 조건이 없으므로 포인터는 항목 $3$으로 이동한다.