bobo 在坐标轴上画了 $n$ 个区间，这些区间被依次编号为 $1, 2, \dots, n$。作为一名优秀的数学家，他设法使所有 $n$ 个区间的长度均为 $10^6$。

然后，bobo 仔细计算了 $I_{i,j}$，即区间 $i$ 和区间 $j$ 的交集长度，并丢弃了所有区间。然而，bobo 想要检查他的计算结果，他非常想知道该结果是否正确。

换句话说，确定是否存在 $n$ 个长度为 $10^6$ 的区间能产生相同的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$)。

接下来的 $n$ 行，每行包含 $n$ 个整数 $I_{i,1}, I_{i,2}, \dots, I_{i,n}$ ($0 \le I_{i,j} \le 10^6$)。

已知 $I_{i,j} = I_{j,i}$ 且 $I_{i,i} = 10^6$。

输出格式

如果对于给定的 $I_{i,j}$，能够找到至少一组符合条件的区间，则输出 "Yes"。否则，输出 "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