Problem Statement

You are given as input a non-negative integer $N$ and a square matrix $D$ of order $N$ with non-negative integer coefficients.

We define $1.$ non-degeneracy, $2.$ symmetry, $3.$ the triangle inequality, and $4.$ the strong triangle inequality of $D$ as the following properties, respectively.

1. Non-degeneracy: for any positive integers $i$ and $j$ not greater than $N$, $D(i,j) = 0$ and $i = j$ are equivalent.
2. Symmetry: for any positive integers $i$ and $j$ not greater than $N$, $D(i,j) = D(j,i)$.
3. Triangle inequality: for any positive integers $i$, $j$, and $k$ not greater than $N$, $D(i,j) \leq D(i,k) + D(k,j)$.
4. Strong triangle inequality: for any positive integers $i$, $j$, and $k$ not greater than $N$, $D(i,j) \leq \max \{D(i,k),D(k,j)\}$.

Here, for each pair of positive integers $i$ and $j$ not greater than $N$, the $(i,j)$ entry of $D$ (in the $i$-th row from the top) is denoted by $D(i,j)$.

$D$ is a good matrix if $D$ satisfies all of $1.$ non-degeneracy, $2.$ symmetry, and $3.$ the triangle inequality.

$D$ is a super good matrix if $D$ satisfies all of $1.$ non-degeneracy, $2.$ symmetry, and $4.$ the strong triangle inequality.

Determine whether $D$ is a good matrix and whether it is a super good matrix.

Background

In geometry and number theory, the concepts of metric spaces and ultrametric spaces are used extensively. Let $I_N$ be the set of all positive integers not greater than $N$, and regard $D$ as a function of $2$ variables on $I_N$. Then $D$ is a good matrix if and only if $(I_N,D)$ is a metric space, and $D$ is a super good matrix if and only if $(I_N,D)$ is an ultrametric space. Therefore, this problem is equivalent to determining whether $(I_N,D)$ is a metric space and whether it is an ultrametric space.

Input

• Line $1$ contains $N$.
• For each positive integer $i$ not greater than $N$, line $1 + i$ contains $D(i,j)$ for each positive integer $j$ not greater than $N$, in ascending order of $j$, separated by single-byte spaces.

$N$
$D(1,1)$ $\cdots$ $D(1,N)$
$\vdots$
$D(N,1)$ $\cdots$ $D(N,N)$

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $1 \leq N \leq 10$.
• For any positive integers $i$ and $j$ not greater than $N$, $D(i,j)$ is an integer satisfying $0 \leq D(i,j) \leq 10$.

Output

On line $1$, print Yes if $D$ is a good matrix, and No if it is not a good matrix.

On line $2$, print Yes if $D$ is a super good matrix, and No if it is not a super good matrix.

Print a newline at the end.

Sample

1
0

Yes
Yes

1
1

No
No

3
0 1 2
1 0 1
2 1 0

Yes
No

3
0 2 1
2 0 2
1 2 0

Yes
Yes