Anda sedang menelusuri koleksi daring berisi $n$ barang bernomor $1$ hingga $n$ yang disusun melingkar. Barang di sebelah kanan setiap barang $i$ adalah barang $i+1$, dan barang di sebelah kanan barang $n$ adalah barang $1$. Demikian pula, barang di sebelah kiri setiap barang $i$ adalah barang $i-1$, dan barang di sebelah kiri barang $1$ adalah barang $n$.

Barang-barang tersebut memiliki $m$ parameter bernomor $1$ hingga $m$. Nilai parameter $j$ pada barang $i$ adalah bilangan bulat $a_{i,j}$.

Saat Anda menelusuri, pada setiap saat ada penunjuk yang menunjuk suatu barang, yang disebut barang saat ini.

Selain itu, Anda dapat mengelola himpunan kondisi penyaringan. Setiap kondisi adalah pasangan $(j,v)$, yang berarti parameter ke-$j$ barang harus sama dengan $v$. Barang saat ini selalu memenuhi semua kondisi dalam himpunan.

Untuk menelusuri koleksi, Anda dapat melakukan operasi. Setiap operasi harus berupa salah satu dari empat jenis berikut:

• Klik “kanan”. Penunjuk bergerak ke barang terdekat di sebelah kanan barang saat ini yang memenuhi semua kondisi penyaringan. Khususnya, jika barang saat ini adalah satu-satunya barang tersebut, penunjuk tidak bergerak.

• Klik “kiri”. Demikian pula, penunjuk bergerak ke barang terdekat di sebelah kiri barang saat ini yang memenuhi semua kondisi penyaringan, dan tetap di tempat jika barang saat ini adalah satu-satunya barang tersebut.

• Tambahkan kondisi penyaringan baru $(j,v)$, untuk suatu bilangan bulat $j$ dan $v$. Jika barang saat ini memenuhi kondisi ini, penunjuk tidak bergerak. Jika tidak, penunjuk bergerak ke barang terdekat di sebelah kanan barang saat ini yang memenuhi semua kondisi penyaringan, termasuk yang baru. Jika barang tersebut tidak ada, operasi ini tidak sah dan tidak dapat dilakukan.

• Hapus kondisi penyaringan $(j,v)$ mana pun dari himpunan. Penunjuk tidak bergerak.

Untuk setiap pasangan barang terurut $(i,j)$, jawab pertanyaan berikut:

• Jika Anda mulai menelusuri dengan penunjuk pada barang $i$ dan himpunan kondisi penyaringan kosong, berapa banyak operasi minimum yang diperlukan untuk memindahkan penunjuk ke barang $j$? Himpunan kondisi penyaringan pada akhir boleh sembarang.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $m$, yang menyatakan banyaknya barang dalam koleksi dan banyaknya parameter setiap barang ($2\le n\le500$; $1\le m\le5$).

Baris ke-$i$ dari $n$ baris berikutnya berisi $m$ bilangan bulat $a_{i,1},a_{i,2},\ldots,a_{i,m}$, yang menyatakan nilai parameter barang $i$ ($1\le a_{i,j}\le n$).

Keluaran

Cetak $n$ baris yang masing-masing berisi $n$ bilangan bulat.

Bilangan bulat ke-$j$ pada baris ke-$i$ harus sama dengan banyaknya operasi minimum untuk memindahkan penunjuk dari barang $i$ ke barang $j$, dimulai dengan himpunan kondisi penyaringan kosong.

Contoh

Masukan 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

Keluaran 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

Catatan

Pada contoh, salah satu cara tercepat untuk berpindah dari barang 2 ke barang 5 adalah sebagai berikut:

• Tambahkan kondisi penyaringan baru $(3,4)$. Karena barang 2 memang memiliki nilai parameter 3 sama dengan 4, penunjuk tetap pada barang 2.

• Klik “kanan”. Penunjuk bergerak ke barang terdekat di sebelah kanan barang 2 yang memenuhi satu-satunya kondisi aktif $(3,4)$. Barang ini adalah barang 5. (Mengklik “kiri” sebagai gantinya juga bisa.)

Salah satu cara tercepat untuk berpindah dari barang 8 ke barang 3 adalah sebagai berikut:

• Tambahkan kondisi penyaringan baru $(3,4)$. Karena barang 8 tidak memenuhi kondisi ini, penunjuk bergerak ke barang terdekat di sebelah kanan barang 8 yang nilai parameter 3-nya sama dengan 4. Barang ini adalah barang 2.

• Hapus kondisi penyaringan $(3,4)$. Penunjuk tetap pada barang 2.

• Klik “kanan”. Karena tidak ada kondisi penyaringan dalam himpunan, penunjuk bergerak ke barang 3.