시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

문제

Bobo draws $n$ intervals on the axis, which are conveniently numbered by $1, 2, \dots, n$. As an excellent mathematician, he managed to set all $n$ intervals of length $10^6$.

Then bobo carefully computes $I_{i, j}$, the length of the intersection of intervals $i$ and $j$, and discards all intervals. However, bobo wants to check his calculations and he is eager to know whether the result can be correct.

In another word, determine if there exists $n$ intervals of length $10^6$ providing the same result.

입력

The first line contains an integer $n$ ($1 \leq n \leq 1000$).

Each of the following $n$ lines contains $n$ integers $I_{i, 1}, I_{i, 2}, \dots, I_{i, n}$ ($0 \leq I_{i, j} \leq 10^6$).

Since bobo knows math well, it is guaranteed that $I_{i, j} = I_{j, i}$ and $I_{i, i} = 10^6$.

출력

If for given $I_{i,j}$ it is possible to find at least one appropriate set of intervals, print "Yes". Otherwise, print "No".

예제 입력 1

3
1000000 500000 0
500000 1000000 500000
0 500000 1000000

예제 출력 1

Yes

예제 입력 2

3
1000000 500000 500000
500000 1000000 500000
500000 500000 1000000

예제 출력 2

No