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:
import java.io.*;
import java.util.*;
import java.math.*;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class MagicGrid {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }
    static class TaskA {
        long mod = (long)(1000000007);
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            while(testNumber-->0){
            	int n = in.nextInt();
            	int a[][] = new int[n][n];
            	int val = 0;
            	for(int j=0;j<n;j+=4){
            		for(int i=0;i<n;i++){
            			for(int k=0;k<4;k++){
            				a[i][k+j] = val++;
            			}
            		}
            	}
            	print2d(a , out);
            }
        }
        public int lowerBound(ArrayList<Integer> a , int x){
        	int l = 0;
        	int r = a.size()-1;
        	if(a.get(l)>=x)
        		return -1;
        	if(a.get(r)<x)
        		return r;
        	int mid = -1;
        	while(l<=r){
        		mid = (l+r)/2;
        		if(a.get(mid) == x && a.get(mid-1)<x)
        			return mid-1;
        		else if(a.get(mid)>=x)
        			r = mid-1;
        		else if(a.get(mid)<x && a.get(mid+1)>=x)
        			return mid;
        		else if(a.get(mid)<x && a.get(mid+1)<x)
        			l = mid+1;
        	}
        	return mid;
        }
        public int upperBound(ArrayList<Integer> a , int x){
            int l = 0;
            int r = a.size()-1;
            if(a.get(l)>x)
                return l;
            if(a.get(r)<=x)
                return r+1;
            int mid = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(a.get(mid) == x && a.get(mid+1)>x)
                    return mid+1;
                else if(a.get(mid)<=x)
                    l = mid+1;
                else if(a.get(mid)>x && a.get(mid-1)<=x)
                    return mid;
                else if(a.get(mid)>x && a.get(mid-1)>x)
                    r = mid-1;
            }
            return mid;
        }
        public int log(int x){
		    return (int) Math.ceil((Math.log(x) / Math.log(2)+10e-10));
		}
        public long gcd(long a , long b){
        	if(a<b){
        		long c = b;
        		b = a;
        		a = c;
        	}
        	if(a%b==0)
        		return b;
        	return gcd(b , a%b);
        }
        public void print2d(int a[][] , PrintWriter out){
        	for(int i=0;i<a.length;i++){
        		for(int j=0;j<a[i].length;j++)
        			out.print(a[i][j] + " ");
        		out.println();
        	}
        }
        public void print1d(int a[] , PrintWriter out){
            for(int i=0;i<a.length;i++)
                out.print(a[i] + " ");
            out.println();
            out.println();
        }
        class Combine{
            int value , delete;
            Combine(int val , int delete){
                this.value = val;
                this.delete = delete;
            }
        }
        class Sort2 implements Comparator<Combine>{
            public int compare(Combine a , Combine b){
                if(a.value > b.value)
                    return 1;
                else if(a.value == b.value && a.delete>b.delete)
                    return 1;
                return -1;
            }
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}