Problem H
Excursion

When Ellinor travels, she likes to go on adventures. Right now, she is located at the top-left cell in an $R \times R$ grid. She wants to reach the bottom-right cell. To do this, she will perform a walk, where she only moves to the right or downward. Each cell contains a point of interest, numbered from $0$ to $R \cdot R - 1$. The same point of interest can appear in multiple cells. She considers a walk to be interesting if all points of interest along the way are unique, that is, she never visits the same point of interest twice. If Ellinor performs her walk completely at random, is it guaranteed to be interesting?

Input

The first line of input contains the integer $R$ ($1 \leq R \leq 1000$), the number of rows in the grid.

Next, the grid is described. Each of the following $R$ rows each contain $R$ integers from $0$ to $R \times R-1$, the attractions of the row.

Note that this problem has a very large input size. Therefore, it is recommended to use fast input reading.

Output

If Ellinor’s walk will be interesting irregardless of how she does it, print 1. Otherwise, print 0.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Explanation of Samples

Sample 1: since all landmarks are unique, there is no risk of seeing the same landmark twice.

Sample 2: even though landmark $1$ appears twice, it is impossible to see it twice.

Sample 3: if Ellinor is unlucky, she first goes down and then to the right, thereby seeing landmark $1$ twice. Thus, not all possible walks are interesting.

Sample 4: Ellinor’s start and end tiles both contain landmark $0$, so no walk is interesting.

2
0 1
2 3

1

2
0 1
1 2

1

2
0 2
1 1

0

2
0 1
1 0

0

1
0

1