Bạn đang duyệt một bộ sưu tập trực tuyến gồm $n$ vật phẩm được đánh số từ $1$ đến $n$ và xếp thành vòng tròn. Vật phẩm bên phải mỗi vật phẩm $i$ là vật phẩm $i+1$, và vật phẩm bên phải vật phẩm $n$ là vật phẩm $1$. Tương tự, vật phẩm bên trái mỗi vật phẩm $i$ là vật phẩm $i-1$, và vật phẩm bên trái vật phẩm $1$ là vật phẩm $n$.

Các vật phẩm có $m$ tham số được đánh số từ $1$ đến $m$. Giá trị tham số $j$ của vật phẩm $i$ là số nguyên $a_{i,j}$.

Trong khi duyệt, tại mọi thời điểm có một con trỏ trỏ vào một vật phẩm, được gọi là vật phẩm hiện tại.

Ngoài ra, bạn có thể quản lý một tập các điều kiện lọc. Mỗi điều kiện là một cặp $(j,v)$, nghĩa là tham số thứ $j$ của vật phẩm phải bằng $v$. Vật phẩm hiện tại luôn thỏa mãn mọi điều kiện trong tập.

Để duyệt bộ sưu tập, bạn có thể thực hiện các thao tác. Mỗi thao tác phải thuộc một trong bốn loại sau:

• Nhấn “phải”. Con trỏ di chuyển đến vật phẩm gần nhất bên phải vật phẩm hiện tại thỏa mãn mọi điều kiện lọc. Đặc biệt, nếu vật phẩm hiện tại là vật phẩm duy nhất như vậy, con trỏ không di chuyển.

• Nhấn “trái”. Tương tự, con trỏ di chuyển đến vật phẩm gần nhất bên trái vật phẩm hiện tại thỏa mãn mọi điều kiện lọc, và đứng yên nếu vật phẩm hiện tại là vật phẩm duy nhất như vậy.

• Thêm một điều kiện lọc mới $(j,v)$, với các số nguyên $j$ và $v$ nào đó. Nếu vật phẩm hiện tại thỏa mãn điều kiện này, con trỏ không di chuyển. Ngược lại, con trỏ di chuyển đến vật phẩm gần nhất bên phải vật phẩm hiện tại thỏa mãn mọi điều kiện lọc, kể cả điều kiện mới. Nếu không có vật phẩm như vậy, thao tác không hợp lệ và không thể thực hiện.

• Xóa bất kỳ điều kiện lọc $(j,v)$ nào khỏi tập. Con trỏ không di chuyển.

Với mỗi cặp vật phẩm có thứ tự $(i,j)$, hãy trả lời câu hỏi sau:

• Nếu bắt đầu duyệt với con trỏ ở vật phẩm $i$ và tập điều kiện lọc rỗng, số thao tác ít nhất cần để chuyển con trỏ đến vật phẩm $j$ là bao nhiêu? Tập điều kiện lọc khi kết thúc có thể tùy ý.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$, cho biết số vật phẩm trong bộ sưu tập và số tham số của mỗi vật phẩm ($2\le n\le500$; $1\le m\le5$).

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa $m$ số nguyên $a_{i,1},a_{i,2},\ldots,a_{i,m}$, cho biết các giá trị tham số của vật phẩm $i$ ($1\le a_{i,j}\le n$).

Dữ liệu ra

In ra $n$ dòng, mỗi dòng chứa $n$ số nguyên.

Số nguyên thứ $j$ trên dòng thứ $i$ phải bằng số thao tác ít nhất cần để chuyển con trỏ từ vật phẩm $i$ đến vật phẩm $j$, bắt đầu với tập điều kiện lọc rỗng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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

Ghi chú

Trong ví dụ, một cách nhanh nhất có thể để chuyển từ vật phẩm 2 đến vật phẩm 5 là:

• Thêm điều kiện lọc mới $(3,4)$. Vì giá trị tham số 3 của vật phẩm 2 đúng là bằng 4, con trỏ đứng yên ở vật phẩm 2.

• Nhấn “phải”. Con trỏ di chuyển đến vật phẩm gần nhất bên phải vật phẩm 2 thỏa mãn điều kiện đang có hiệu lực duy nhất $(3,4)$. Đó là vật phẩm 5. (Thay bằng nhấn “trái” cũng được.)

Một cách nhanh nhất có thể để chuyển từ vật phẩm 8 đến vật phẩm 3 là:

• Thêm điều kiện lọc mới $(3,4)$. Vì vật phẩm 8 không thỏa mãn điều kiện này, con trỏ di chuyển đến vật phẩm gần nhất bên phải vật phẩm 8 có giá trị tham số 3 bằng 4. Đó là vật phẩm 2.

• Xóa điều kiện lọc $(3,4)$. Con trỏ đứng yên ở vật phẩm 2.

• Nhấn “phải”. Vì tập không có điều kiện lọc nào, con trỏ di chuyển đến vật phẩm 3.