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

  * All integers from 0 to (n^2 - 1) inclusive appear in the matrix exactly once. 
  * [Bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#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 × n.

Input

The only line of input contains an integer n (4 ≤ n ≤ 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.

Examples

Input


4


Output


8 9 1 13
3 12 7 5
0 2 4 11
6 10 15 14

Input


8


Output


19 55 11 39 32 36 4 52
51 7 35 31 12 48 28 20
43 23 59 15 0 8 16 44
3 47 27 63 24 40 60 56
34 38 6 54 17 53 9 37
14 50 30 22 49 5 33 29
2 10 18 46 41 21 57 13
26 42 62 58 1 45 25 61

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.
import sys
import math
from collections import defaultdict,deque
n=int(sys.stdin.readline())
arr=[[0 for _ in range(n)] for x in range(n)]
count=0
num=0
for i in range(n//2):
    for j in range(n//2):
        arr[i][j]=num
        num+=1
        arr[i][j]=arr[i][j]*4+count
count=1
num=0
for i in range(n//2,n):
    for j in range(n//2):
        arr[i][j]=num
        num+=1
        arr[i][j]=arr[i][j]*4+count
count=2
num=0
for i in range(n//2):
    for j in range(n//2,n):
        arr[i][j]=num
        arr[i][j]=arr[i][j]*4+count
        num+=1
count=3
num=0
for i in range(n//2,n):
    for j in range(n//2,n):
        arr[i][j]=num
        arr[i][j]=arr[i][j]*4+count
        num+=1
for i in range(n):
    print(*arr[i])
