Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by n square grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and a_x, y ≠ 1, there should exist two indices s and t so that a_x, y = a_x, s + a_t, y, where a_i, j denotes the integer in i-th row and j-th column.

Help Okabe determine whether a given lab is good!

The first line of input contains the integer n (1 ≤ n ≤ 50) — the size of the lab.

The next n lines contain n space-separated integers denoting a row of the grid. The j-th integer in the i-th row is a_i, j (1 ≤ a_i, j ≤ 10⁵).

Print "Yes" if the given lab is good and "No" otherwise.

You can output each letter in upper or lower case.