Problem: 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.

Solution (in JAVA):

Solution:
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x1208C
   {
      static int[][] four = {{8,9,1,13},
                             {3,12,7,5},
                             {0,2,4,11},
                             {6,10,15,14}};
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[][] grid = new int[N][N];
         for(int r=0; r < 4; r++)
            for(int c=0; c < 4; c++)
               grid[r][c] = four[r][c];
         for(int r=0; r < 4; r++)
            for(int c=0; c < 4; c++)
            {
               int addend = 16;
               int row = r+4;
               int col = c;
               while(col < N)
               {
                  while(row < N)
                  {
                     grid[row][col] = grid[r][c]+addend;
                     row += 4;
                     addend += 16;
                  }
                  row = r;
                  col += 4;
               }
            }
         for(int r=0; r < N; r++)
         {
            for(int x: grid[r])
               sb.append(x+" ");
            sb.append("\n");
         }
         System.out.print(sb);
      }
   }