Given an undirected complete graph with $n$ vertices and positive edge weights, for each edge $(a, b)$, determine whether there exists a pair of vertices $(x, y)$ such that all shortest paths from $x$ to $y$ pass through $(a, b)$.

Input

The input is read from standard input.

The first line contains a positive integer $n$ ($1 \le n \le 500$), representing the number of vertices in the graph.

The next $n$ lines each contain $n$ integers, forming an $n \times n$ matrix. The $j$-th number in the $i$-th row, $a_{i,j}$ ($1 \le a_{i,j} \le 10^6$), represents the length of the edge between $i$ and $j$. Specifically, $a_{i,i} = 0$.

It is guaranteed that $a_{i,j} = a_{j,i}$.

Output

The output is written to standard output.

Output an $n \times n$ binary matrix, where the entry in the $i$-th row and $j$-th column is $1$ if the edge $(i, j)$ satisfies the condition stated in the problem, and $0$ otherwise.

Specifically, output $0$ when $i = j$.

Examples

Input 1

4
0 3 2 100
3 0 8 100
2 8 0 10
100 100 10 0

Output 1

0110
1000
1001
0010