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:
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

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

0 4 2 6
8 12 10 14
1 5 3 7
9 13 11 15
 */
public class MagicGrid {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        int block = N / 2;
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < N; j++) {
//                int amt = (i % block) * block + (j % block);
//                int offset = ((i / block) * 2 + j / block) * (block * block);
//                out.print(amt + offset + " ");
//            }
//            out.println();
//        }
        int curr = 0;
        int[][] grid = new int[N][N];
        for (int i = 0; i < block; i++) {
            for (int j = 0; j < block; j++) {
                grid[i][j] += 4 * curr;
                grid[i + block][j] += 4 * curr + 1;
                grid[i][j + block] += 4 * curr + 2;
                grid[i + block][j + block] += 4 * curr + 3;
                curr++;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                out.print(grid[i][j] + " ");
            }
            out.println();
        }
        out.close();
    }

    static class FastScanner {
        public int BS = 1<<16;
        public char NC = (char)0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double cnt = 1;
        BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}