Farmer John의 농장은 서로 다른 정점들을 도로(간선)로 연결한 방향 가중 그래프로 나타낼 수 있다. 각 간선의 가중치는 해당 도로를 따라 이동하는 데 필요한 시간이다. Bessie는 매일 외양간(정점 $1$)에서 들판(정점 $N$)까지 정확히 $K$개의 도로를 따라 이동하기를 좋아하며, 이 조건을 지키면서 최대한 빨리 들판에 도착하고 싶어 한다. 하지만 어느 순간 도로의 유지 보수가 중단되고, 도로들이 하나씩 망가져서 통행할 수 없게 된다. Bessie가 모든 시점에서 외양간에서 들판까지의 최단 경로를 찾도록 도와주자!

정확히 말하면, 처음에는 $N$개의 정점 ($1\le N\le 300$)과 $N^2$개의 간선으로 이루어진 완전 방향 가중 그래프가 있다. 모든 $1 \le i, j \le N$인 쌍 $(i, j)$마다 간선 하나가 있다(자기 루프도 $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$-간선 경로의 가중치를 출력한다. $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