H. Observe
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In order to collect geographical information on Mount Wolwz, a team of geographical observers needed to establish four observation points on the mountain. In order to obtain accurate data, the four observation points need to be exactly the four vertices of a square when viewed from the air. The observation algorithm used by the team required at least three of the observation points to be at the same height. And for the last observation point, which is at a different height to the other three, it needs to be at a higher position than the other three.

The top view of Mount Wolwz can be seen as a square with $$$n*n$$$ small square platforms, where each piece has an integer height. The group discussed that the higher the three observation points of the same height, the better the result. So they wanted to find out what the highest of the three observation points at the same height was.

Input

The input contains a total of $$$n + 1$$$ lines

The first line contains an integer $$$n(2 \leq n \leq 300)$$$, representing the length of the side of Mount Wolwz

Next $$$n$$$ lines, th $$$i$$$-th line contains $$$n$$$ integers:$$$h_{i,1},h_{i,2},...,h_{i,j},...,h_{i,n}(1 \leq h_{i,j} \leq 10^{9})$$$, representing the height of each of the small platforms of Mount Wolwz

Output

One line contains an interger, representing the best height. If suitable observation points cannot be established in Mount Wolwz, output "$$$-1$$$"(without quotes).

Examples
Input
3
1 1 3
1 2 2
3 2 3
Output
2
Input
3
1 2 1
2 2 2
1 2 1
Output
-1
Note

In the first example, $$$[(1,1),(1,2),(2,1),(2,2)]$$$ and $$$[(2,2),(3,2),(2,3),(3,3)]$$$ are all suitable observation point combinations.