The Slovak company WKD (Wiosła Kardynalnie Dobre) has produced $n$ new types of oars! The company does not have a good method for measuring the lift force of its products, so it hired a professional oar tester, Słowomir. Unfortunately, his way of determining the lift force of the oars is not very accurate either—he takes every possible pair of oars, gets into a boat, and rows to a buoy and back. Then he writes down: I am sure that the total force of the oars did not exceed $x$, but one of them definitely had a force of at least $y$, because my arm got tired. After finishing the tests, Słowomir handed the results to Mirosława, the head of WKD. However, she thinks there is too much data and, furthermore, it is not very meaningful. She would prefer to know any sequence of lift force values that would be consistent with the tester's results. Provide such a sequence.

Input

The first line of input contains an integer $n$ ($1 \le n \le 300$), representing the number of oar types. The oar types are numbered from 1 to $n$. The next $n$ lines each contain $n$ numbers: the $j$-th number in the $i$-th line is $x_{ij}$ ($1 \le x_{ij} \le 10^{9}$), which is the upper bound on the total lift force of oars of types $i$ and $j$. The next line is empty. Following that, there are again $n$ lines, each with $n$ numbers. The number in the $i$-th line at position $j$ is $y_{ij}$ ($1 \le y_{ij} \le 10^{9}$). It means that the oar of type $i$ or the oar of type $j$ has a lift force of at least $y_{ij}$.

Output

Output $n$ positive integers: the $i$-th number should represent the lift force of the oar of type $i$ in a sequence of lift force values consistent with the information provided by Słowomir. You may assume that a valid solution exists.

Examples

Input 1

3
6 8 5
7 6 6
5 7 7

2 3 1
3 1 1
2 1 3

Output 1

2 3 3