Farmer John 的農場可以表示為一張有向帶權圖，道路（邊）連接不同節點，每條邊的權重就是沿該道路行進所需的時間。每天，Bessie 都喜歡從穀倉（位於節點 $1$）出發，恰好經過 $K$ 條道路到達田地（位於節點 $N$），並希望在此限制下儘快到達田地。然而，某個時刻起，道路不再受到維護，開始一條接一條地損壞，變得無法通行。請幫助 Bessie 找出每個時刻從穀倉到田地的最短路徑！

形式化地說，一開始有一張包含 $N$ 個頂點（$1\le N\le 300$）、$N^2$ 條邊的完全有向帶權圖：對每一對 $(i, j)$（$1 \le i, j \le N$）都有一條邊（注意其中有 $N$ 個自環）。每次刪除一條邊後，輸出從 $1$ 到 $N$、恰好經過 $K$ 條邊（不必互不相同）的路徑的最小權重（$2\le K\le 8$）。注意，第 $i$ 次刪除後，圖中剩下 $N^2-i$ 條邊。

一條路徑的權重定義為該路徑上所有邊的權重總和。注意，路徑可以多次經過同一條邊，也可以多次經過同一個頂點，包括頂點 $1$ 和 $N$。

輸入格式

第一行包含 $N$ 和 $K$。

接下來 $N$ 行，每行包含 $N$ 個整數。第 $i$ 行的第 $j$ 個整數為 $w_{ij}$（$1\le w_{ij}\le 10^8$）。

接著有 $N^2$ 行，每行包含兩個整數 $i$ 和 $j$（$1\le i,j\le N$）。每一對整數恰好出現一次。

輸出格式

恰好輸出 $N^2$ 行，表示每次刪除後恰好經過 $K$ 條邊的路徑的最小權重。如果不存在這樣的路徑，則輸出 $-1$。

範例

輸入格式 1

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

輸出格式 1

11
18
22
22
22
-1
-1
-1
-1

說明

第一次刪除後，恰好經過 $4$ 條邊的最短路徑為：

1 -> 2 -> 3 -> 2 -> 3

第二次刪除後，恰好經過 $4$ 條邊的最短路徑為：

1 -> 3 -> 2 -> 1 -> 3

第三次刪除後，恰好經過 $4$ 條邊的最短路徑為：

1 -> 3 -> 3 -> 3 -> 3

刪除六次後，不再存在恰好經過 $4$ 條邊的路徑。

子任務

• 對於 $2\le T\le 14$，測試資料 $T$ 滿足 $K=\lfloor (T+3)/2\rfloor$。

題目作者：Benjamin Qi