Floyd - 1

A complete directed weighted graph is given by its adjacency matrix. Construct a matrix of the shortest paths between all pairs of its vertices. It is guaranteed that the graph has no cycles of negative weight.

Input

The first line contains the number of vertices $n(1\le n\le 100)$ in the graph. Each of the next $n$ lines contains $n$ integers and describes the adjacency matrix of the graph (the $j$-th number in the $i$-th row corresponds to the weight of the edge from vertex $i$ to vertex $j$). All numbers by the absolute value do not exceed $100$. The diagonal elements of the matrix are always zeros.

Output

Print $n$ lines with $n$ integers — the matrix of the shortest distances between all pairs of vertices. The $j$-th number in the $i$-th row should equal the weight of the shortest path from vertex $i$ to vertex $j$.

Examples