← 返回题目列表

Codeforces · 821/A

A. 冈部和未来小工具实验室

中文机器翻译题面 查看原题

冈部在尝试做一些疯狂的实验后需要翻新未来小工具实验室!实验室表示为 n × n 的整数方形网格。一个好的实验室被定义为一个实验室,其中每个不等于 1 的数字都可以表示为同一行中的一个数字与同一列中的一个数字之和。换句话说,对于每个满足 1 ≤ x, y ≤ n 且 ax, y ≠ 1 的 x, y,应该存在两个索引 s 和 t,使得 ax, y = ax, s + at, y,其中 ai, j 表示第 i 行第 j 列的整数。

帮助冈部确定给定的实验室是否良好!

输入

输入的第一行包含整数 n (1 ≤ n ≤ 50) — 实验室的大小。

接下来的 n 行包含 n 个空格分隔的整数,表示网格的一行。第 i 行中的第 j 个整数为 ai, j (1 ≤ ai, j ≤ 105)。

输出

如果给定的实验室良好,则打印“是”,否则打印“否”。

您可以以大写或小写形式输出每个字母。

示例

输入 #1

3
1 1 2
2 3 1
6 4 1

输出 #1

Yes

输入 #2

3
1 5 2
1 1 1
1 2 3

输出 #2

No

注意

在第一个样本测试中,左下角的6是有效的,因为它是它上面的2和右边的4的和。对于此表中每个不等于 1 的数字也是如此,所以答案是“是”。

在第二个样本测试中,5 不能形成为同一行中的一个整数与同一列中的一个整数之和。因此答案是“否”。