The main products of High-Integrity Integer Ternaries (HIIT) are ternary squares that are grids of n rows and columns whose cells are filled with numbers 0, 1, and 2. A customer has requested a very special ternary square: the 2n sums obtained from each row and column should be distinct. Your job is to figure out if such a ternary square is possible.

Input

The only line of the input contains a single integer n.

Output

If no solution exists, output "IMPOSSIBLE".

Otherwise, output "YES" on a single line. Then, output n lines, each describing one row of the square.

Constraints

• 1 \le n \le 1000

Examples

Input:

1

Output:

IMPOSSIBLE

Input:

2

Output:

YES
1 2
0 0