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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Math.*;
import static java.lang.System.out;
import java.util.*;
import java.io.PrintStream;
import java.io.PrintWriter;
public class A {
 
	static final int mod = 1000000007;
	static final long temp = 998244353;
	static final long MOD = 1000000007;
	static final long M = (long)1e9+7;
 
	
	static class Pair implements Comparable<Pair>
	{
		int first, second;
		public Pair(int aa, int bb)
		{
			first = aa; second = bb;
		}
		public int compareTo(Pair p)
		{
			if(first == p.first) return (int)(second - p.second);
			return (int)(first - p.first);
		}
	}
	
	/*
	 * IO FOR 2D GRID IN JAVA
	 * 	char[][] grid = new char[n][m];
			for(int i = 0;i<n;i++)
			{
				char[] s = sc.next().toCharArray();
				for(int j = 0;j<m;j++)
				{
					grid[i][j] = s[j];
				}
			}
	 * */
	
	static class Reader {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		int[] readArray(int n) throws IOException {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		long[] longReadArray(int n) throws IOException {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
		
		
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
	
 
		public static boolean isPrime(int n) 
		{
			if(n == 1)
			{
				return false;
			}
			for(int i = 2;i*i<=n;i++)
			{
				if(n%i == 0)
				{
					return false;
				}
			}
			return true;
	}
	
	public static List<Integer> Sieve(int n)
	{
		boolean prime[] = new boolean[n+1];
		Arrays.fill(prime, true);
		
		List<Integer> l = new ArrayList<>();
		for (int p=2; p*p<=n; p++) 
		{ 
			if (prime[p] == true) 
			{ 	
			    for(int i=p*p; i<=n; i += p) 
				{
				    prime[i] = false; 
				}	
			} 
		} 
 
		for (int p=2; p<=n; p++) 
		{
		    if (prime[p] == true)
		    {
		       l.add(p); 
		    }
		}
		
		return l;
	}
	
	
	public static int gcd(int a, int b)
	{
		if(b == 0)
		 return a;
		
		else
		return gcd(b,a%b);
	} 
 
	public static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
	
	public static long LongGCD(long a, long b)
	{
		if(b == 0)
			 return a;
			
			else
			return LongGCD(b,a%b);
	}
	
	public static long LongLCM(long a, long b)
    {
        return (a / LongGCD(a, b)) * b;
    }
	
	public static int phi(int n)  //euler totient function
    { 
        int result = 1; 
        for (int i = 2; i < n; i++) 
            if (gcd(i, n) == 1) 
                result++; 
        return result; 
    }
	
	public static long fastPow(long x, long n) //include mod at each step if asked and in args of fn too
	{
		if(n == 0)
			return 1;
		else if(n%2 == 0)
			return fastPow(x*x,n/2);
		else
			return x*fastPow(x*x,(n-1)/2);
	}
	
	
	   public static long modPow(long x, long y, long p)
	    {
	        long res = 1;
	        x = x % p;
	 
	        while (y > 0) {
	            if (y % 2 == 1)
	                res = (res * x) % p;
	 
	            y = y >> 1; 
	            x = (x * x) % p;
	        }
	        return res;
	    }
	   
	   static long modInverse(long n, long p)
	    {
	        return modPow(n, p - 2, p);
	    }
	 
	    // Returns nCr % p using Fermat's little theorem.
	    
	    public static long nCrModP(long n, long r,long p)
	    {
	          if (n<r) 
	              return 0;
	          
	        if (r == 0)
	            return 1;
	 
	        long[] fac = new long[(int)(n) + 1];
	        fac[0] = 1;
	 
	        for (int i = 1; i <= n; i++)
	            fac[i] = fac[i - 1] * i % p;
	 
	        return (fac[(int)(n)] * modInverse(fac[(int)(r)], p)
	                % p * modInverse(fac[(int)(n - r)], p)
	                % p)
	            % p;
	    }
	    
	    public static long nCr(long n, long r)
	    {
	    	long ans = 1;
	    	for(long i = 1,j = n;i<=r;i++,j--)
	    	{
	    		ans = ans * j / i;
	    	}
	    	return ans;
	    }
 
		public static void Sort(long[] a) {
			List<Long> l=new ArrayList<>();
			for (long i : a) l.add(i);
			Collections.sort(l);
			Collections.reverse(l);  //Use to Sort decreasingly 
			for (int i=0; i<a.length; i++) a[i]=l.get(i);
		}
		
		
		//Modular Operations for Addition and Multiplication. 
		
		   public static long perfomMod(long x)
		   {
		        return ((x%M + M)%M);
		    }
		   public static long addMod(long a, long  b)
		   {
		        return perfomMod(perfomMod(a)+perfomMod(b));
		    }
		   public static long mulMod(long  a, long b)
		   {
		        return perfomMod(perfomMod(a)*perfomMod(b));
		   }
		
		   public static int LowerBound(int a[], int x) 
		   {
				  int l=-1,r=a.length;
				  while(l+1<r) {
				    int m=(l+r)>>>1;
				    if(a[m]>=x) r=m;
				    else l=m;
				  }
				  return r;
			}
		
		   
			public static int UpperBound(int a[], int x) 
			{
			    int l=-1;
			    int r=a.length;
			    while(l+1<r) {
			       int m=(l+r)>>>1;
			       if(a[m]<=x) l=m;
			       else r=m;
			    }
			    return l+1;
			}
	
	public static void main(String[] args) throws IOException 
	{
		Reader sc = new Reader();
		PrintWriter fout = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		int[][] a = new int[n][n];
		int c = 0;
		
		for(int i = 0;i<n;i+=4)
		{
			for(int j = 0;j<n;j+=4)
			{
				for(int dx = i;dx<i + 4;++dx)
				{
					for(int dy = j;dy<j+4;++dy)
					{
						a[dx][dy] = (c++);
					}
				}
			}
		}
		
		for(int i = 0;i<n;i++)
		{
			for(int j = 0;j<n;j++)
			{
				fout.print(a[i][j] + " ");
			}
			fout.println();
		}
		
		fout.close();
		
	}
	
}