Road Construction

Limits: 2 sec., 256 MiB

Today Zenyk and Marichka have unique chance to build roads between cities.

There are $N$ cities. Initially there are no roads between them. Every road should be from some city $v$ to some city $u$ with some positive integer length $c$. Zenyk and Marichka can choose this values for every road. Marichka calls a road system good if the following conditions hold:

• There are no road from some city to itself.

• Length of each road is positive integer.

• At most one road can be from any city $v$ to any city $u$.

• The length of the shortest path from city $1$ to city $i$ should be equal to $d_i$.

• Number of distinct shortest pathes from city $1$ to $i$ should be equal to $c_i$.

Help them to find such road system or tell if there is no possible configurations. If there are several answers you can output any of them.

Input

First line contains one integer $N$. Next $N-1$ lines contain 2 integers $d_i$, $c_i$ for cities from $2$ to $N$.

Output

Print “YES“ if good road system exists and “NO“, otherwise. If answer is YES print $N$ lines with $N$ integers in each line. $j$-th number in $i$-th line should be equal to the length of the road from city $i$ to city $j$ if such road exists and $-1$, otherwise.

Constraints

$1 \le N \le 500$,

$1 \le d_i,c_i \le 10^9$.

Samples