Trang trại của Farmer John có thể được mô phỏng như một đồ thị có hướng với trọng số, với các con đường (cạnh) kết nối các nút khác nhau, và trọng số của mỗi cạnh là thời gian cần thiết để di chuyển trên con đường đó. Mỗi ngày, Bessie thích di chuyển từ chuồng (nằm ở nút \(1\)) đến cánh đồng (nằm ở nút \(N\)) bằng cách đi qua chính xác \(K\) con đường, và muốn đến cánh đồng nhanh nhất có thể dưới ràng buộc này. Tuy nhiên, tại một thời điểm nào đó, các con đường sẽ ngừng được bảo trì, và một cách tuần tự, chúng bắt đầu hỏng, trở nên không thể đi qua. Hãy giúp Bessie tìm đường đi ngắn nhất từ chuồng đến cánh đồng vào mọi thời điểm!

Cụ thể, chúng ta bắt đầu với một đồ thị \(N\) đỉnh (\(1\le N\le 300\)) có hướng hoàn chỉnh có trọng số với \(N^2\) cạnh: một cạnh cho mỗi cặp \((i, j)\) với \(1 \le i, j \le N\) (lưu ý rằng có \(N\) vòng lặp tự thân). Sau mỗi lần loại bỏ, hãy xuất ra trọng số tối thiểu của bất kỳ đường đi nào từ \(1\) đến \(N\) đi qua chính xác \(K\) (\(2\le K\le 8\)) cạnh (không nhất thiết phải khác nhau). Lưu ý rằng sau lần loại bỏ thứ \(i\), đồ thị còn lại \(N^2-i\) cạnh.

Trọng số của một đường đi được định nghĩa là tổng trọng số của tất cả các cạnh trên đường đi. Lưu ý rằng một đường đi có thể chứa nhiều cạnh giống nhau và nhiều đỉnh giống nhau, bao gồm cả các đỉnh \(1\) và \(N\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
• \(N\) dòng tiếp theo, mỗi dòng có \(N\) số nguyên. Số nguyên thứ \(j\) của dòng \(i\) là \(w_{ij}\) (\(1\le w_{ij}\le 10^8\)).
• Sau đó là \(N^2\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(j\) (\(1\le i,j\le N\)). Mỗi cặp số nguyên xuất hiện chính xác một lần.

Output

• Chính xác \(N^2\) dòng, trọng số tối thiểu của đường đi \(K\) sau mỗi lần loại bỏ. Nếu không còn đường đi \(K\) nào tồn tại thì xuất ra \(-1\).

Scoring

• Subtask 1: \(K=\lfloor (T+3)/2\rfloor\).
• Subtask 2: Không có ràng buộc gì thêm.

Example

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

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