Wooden Matrix
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Consider a square matrix of size $$$n \times n$$$ consisting of non-negative integers. The matrix is symmetric with respect to the main diagonal, and the main diagonal itself contains only zeroes. Such a matrix is called wooden if there is an undirected tree $$$T$$$ on $$$n$$$ vertices with edges of positive lengths such that each cell $$$(i, j)$$$ of the matrix contains the distance between vertices $$$i$$$ and $$$j$$$ in this tree.

You are given a matrix. Check if it is wooden.

Input

The first line contains an integer $$$n$$$: the size of the matrix ($$$1 \le n \le 1000$$$). Each of the following $$$n$$$ lines contains $$$n$$$ integers $$$d_{i,j}$$$: the elements of the matrix ($$$0 \le d_{i,j} \le 10^9$$$). The matrix is symmetric with respect to the main diagonal. There are zeros on the main diagonal and strictly positive integers outside it.

Output

Print "Yes" or "No" depending on whether the matrix is wooden. Letter case does not matter.

Examples

Input
3
0 1 3
1 0 2
3 2 0
Output
Yes 
Input
3
0 1 3
1 0 1
3 1 0
Output
No