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.math.BigInteger;
import java.util.*;
import java.util.function.Function;
import java.util.function.ToIntFunction;


public class GFGM
{
    static int mod1 = (int) (1e9 + 7);

    static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do
            {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }

        public int[] nextArray(int n) throws IOException
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = nextInt();
            }
            return a;
        }
    }

    static Set<Long> divisor(Set<Long> set0, long num0)
    {
        set0.add(1L);
        long num00=(long)(Math.sqrt(num0))+1;
        for (long i = 2; i<num00; i++)
        {
            if (num0 % i == 0)
            {
                set0.add(i);
                set0.add(num0/i);
            }
        }
        return set0;
    }
    static long primeDivisor(long num0)
    {
        HashMap<Long,Integer> hMap1=new HashMap<>();
        boolean b0=false;
        boolean b1=primeCheck(num0);
        if(b1)
        {
            hMap1.put(0L,1);
        }
        else
        {
            for (long i = 2; i * i <= num0; i++)
            {
                while (num0 % i == 0)
                {
                    if (hMap1.containsKey(i))
                    {
                        hMap1.replace(i,(hMap1.get(i)+1));
                    }
                    else
                    {
                        hMap1.put(i,1);
                    }
                    num0 = num0 / i;
                }

            }
            boolean b2=primeCheck(num0);
            if(b2 && num0!=1)
            {
                if(hMap1.containsKey(num0))
                {
                    hMap1.replace(num0,(hMap1.get(num0)+1));
                }
                else
                {
                    hMap1.put(num0,1);
                }
            }
        }



        return 0;
    }


    static long power2(long x, long y, long p)
    {
        long res = 1;
        x = x % p;
        while (y > 0)
        {
            if ((y & 1) == 1)
            {
                BigInteger res0 = BigInteger.valueOf(res);
                res0 = res0.multiply(BigInteger.valueOf(x));
                res0 = res0.mod(BigInteger.valueOf(p));
                String str0 = res0.toString();
                res = Long.parseLong(str0);
            }
            y = y >> 1;
            BigInteger res00 = BigInteger.valueOf(x);
            res00 = res00.multiply(BigInteger.valueOf(x));
            res00 = res00.mod(BigInteger.valueOf(p));
            String ans00 = res00.toString();
            x = Long.parseLong(ans00);

        }
        return res;
    }

    static long GCD(long num0, long num00)
    {
        BigInteger big1 = BigInteger.valueOf(num0);
        BigInteger big2 = BigInteger.valueOf(num00);
        big1 = big1.gcd(big2);
        long num000 = Long.parseLong(big1.toString());
        return num000;
    }

    static boolean primeCheck(long num0)
    {
        boolean b1 = true;
        if(num0==1)
        {
            b1=false;
        }
        else
        {
            int num01 = (int) (Math.sqrt(num0)) + 1;
            me1: for (int i = 2; i < num01; i++)
            {
                if (num0 % i == 0)
                {
                    b1 = false;
                    break me1;
                }
            }
        }
        return b1;
    }

    static double getTime()
    {
        return System.nanoTime();
    }

    static int countSum1(int len0, int[] arr0, int sum0)
    {
        HashMap<Integer, Integer> map1 = new HashMap<>();

        for (int i = 0; i < len0; i++)
        {
            if (!map1.containsKey(arr0[i]))
            {
                map1.put(arr0[i], 0);
            }
            map1.put(arr0[i], map1.get(arr0[i]) + 1);
        }
        int count0 = 0;
        for (int i = 0; i < len0; i++)
        {
            if (map1.get(sum0 - arr0[i]) != null)
                count0 += map1.get(sum0 - arr0[i]);
            if (sum0 - arr0[i] == arr0[i])
                count0--;
        }
        int num7 = count0 / 2;
        return num7;
    }


/*
    static ArrayList<Long> primeDevisor(ArrayList<Long> arrLst0,long num0)
    {
        arrLst0.add(1L);
        arrLst0.add(num0);

        me1: for (long i = 2; i * i < num0+1; i++)
            {
                while (num0 % i == 0)
                {
                    if(!arrLst0.contains(i))
                    {
                        arrLst0.add(i);
                    }
                    num0 = num0 / i;
                }
            }
            boolean b2=primeCheck(num0);
            if(b2 && num0!=1)
            {
                if(!arrLst0.contains(num0))
                {
                    arrLst0.add(num0);
                }
            }
        }
        return arrLst0;
    }
*/





    public static void main(String[] args) throws IOException
    {
        //double tTime   = getTime()-(startTime);
        //out1.print(tTime/(1e9)+" ");
        Reader r = new Reader();
        //Scanner r = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        //Scanner r=new Scanner(System.in);
        OutputWriter3 out1 = new OutputWriter3(System.out);

        int num1=r.nextInt();
        int[][] arr1=new int[num1][num1];
        int par0=0;
        for(int i=0;i<num1;i+=4)
        {
            int par1=0;
            for(int j=0;j<num1;j+=4)
            {
                for(int m=i;m<i+4;m++)
                {
                    for(int n=j;n<j+4;n++)
                    {
                        arr1[m][n]=par0++;
                    }
                }
            }
        }
        for(int i=0;i<num1;i++)
        {
            for(int j=0;j<num1;j++)
            {
                out1.print(arr1[i][j]+" ");
            }
            out1.print("\n");
        }

        r.close();
        out1.close();
    }
}

class OutputWriter3
{
    BufferedWriter writer;

    public OutputWriter3(OutputStream stream)
    {
        writer = new BufferedWriter(new OutputStreamWriter(stream));
    }

    public void print(int i) throws IOException
    {
        writer.write(i + "");
    }

    public void println(int i) throws IOException
    {
        writer.write(i + "\n");
    }

    public void print(String s) throws IOException
    {
        writer.write(s + "");
    }

    public void println(String s) throws IOException
    {
        writer.write(s + "\n");
    }

    public void print(char[] c) throws IOException
    {
        writer.write(c);
    }

    public void close() throws IOException
    {
        writer.close();
    }
}


class Node
{
    Node left,right;
    int data;
}

class hellos
{
    boolean check(Node root,int min1,int max1)
    {
        if(root==null)
        {
            return true;
        }
        if(root.data<min1 || root.data>=max1)
        {
            return false;
        }
        boolean bool1=check(root.left,min1,Math.min(max1,root.data));
        boolean bool2=check(root.right,Math.min(min1,root.data),max1);
        return bool1&bool2;
    }
}