Star Routes
Space travelers found information about routes between star gates. Using the gates it is possible to get to another world through space hypertunnels. The routes between gates, that are existing in different worlds, represented by matrices. All gates have numbers (1 ≤ i ≤ 100). Route matrix has 1 (one) in (i,j)position, if there is direct route from gate (i) to gate (j).
All other positions contain 0 (zero). Existence of the direct route from gate (i) to gate (j) does not guarantee existence of such route from (j) to (i). But there is always 1 in (i,i) position.
The problem is in following. Using given route matrices you have to find advanced route matrix, that shows all possible routes. This matrix can give information whether gate (k) is reachable from any other gate (i). That is if route from gate (i) to gate (j) exists and route from gate (j) to gate (k)exists, then route from (i) to (k) exists too. An existence of route is also represented by 1 in appropriate matrix position.
So advanced route can be not only direct but can contain intermediate gates.
Input
The first line contains matrix dimension M (M ≤ 100), next lines contain matrix rows. The elements in rows are separated by one space. Input data are correct.
Output
The output is advanced route matrix, one row per line, elements are separated by one space.