Let us define a magic grid to be a square matrix of integers of size $n \times n$, satisfying the following conditions.

• All integers from $0$ to $(n^2 - 1)$ inclusive appear in the matrix exactly once.
• Bitwise XOR of all elements in a row or a column must be the same for each row and column.

You are given an integer $n$ which is a multiple of $4$. Construct a magic grid of size $n \times n$.

Input

The only line of input contains an integer $n$ ($4 \leq n \leq 1000$). It is guaranteed that $n$ is a multiple of $4$.

Output

Print a magic grid, i.e. $n$ lines, the $i$-th of which contains $n$ space-separated integers, representing the $i$-th row of the grid.

If there are multiple answers, print any. We can show that an answer always exists.

Note

In the first example, XOR of each row and each column is $13$.

In the second example, XOR of each row and each column is $60$.