Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

F. Find the Length
time limit per test
4 seconds (5 seconds for Java)
memory limit per test
256 megabytes
input
standard input
output
standard output

For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.

Input

First line of the input contains one inteter n — number of vertices in the graph (1 ≤ n ≤ 300).

Each of n lines contain n integers, i-th integer in the i-th column is equal to 0 for any i. If for i ≠ j j-th integer in i-th line a ij is equal to  - 1, then vertices i and j are not connected, otherwise they are connected by the edge of weight a ij (1 ≤ a ij ≤ 106).

You may assume that graph does not contain self-loops and a ij = a ji for any 1 ≤ i, j ≤ n.

Output

Print n integers one per line. i-th of those integers must be lentgh of the shortest simple cycle, containig i-th vertice. If no simple cycles contain i-th vertiex, print  - 1 at corresponding line.

Examples
Input
4
0 9 1 1
9 0 -1 1
1 -1 0 -1
1 1 -1 0
Output
11
11
-1
11