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 megabytesinput

standard inputoutput

standard outputFor 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} ≤ 10^{6}).

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/10/2020 15:48:42 (i3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|