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!

Input

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^{5}$).

Output

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

You can output each letter in upper or lower case.

Note

In the first sample test, the $6$ in the bottom left corner is valid because it is the sum of the $2$ above it and the $4$ on the right. The same holds for every number not equal to $1$ in this table, so the answer is "Yes".

In the second sample test, the $5$ cannot be formed as the sum of an integer in the same row and an integer in the same column. Thus the answer is "No".