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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class A, class B, class C>
struct Triple {
  A first;
  B second;
  C third;
  bool operator<(const Triple &t) const {
    if (first != t.first) return first < first.st;
    if (second != t.second) return second < t.second;
    return third < t.third;
  }
};
long long gcd(long long a, long long b) {
  while (a && b)
    if (a > b)
      a = a % b;
    else
      b = b % a;
  return a + b;
}
long long bp(long long a, long long b, long long &md) {
  long long res = 1;
  while (b) {
    if (b & 1) res *= a;
    a *= a;
    a %= md;
    res %= md;
    b >>= 1;
  }
  return res;
}
vector<long long> z_function(string &s) {
  long long n = ((long long)((s).size()));
  vector<long long> ans(n, 0);
  long long l = 0, r = 0;
  for (long long i = 1; i < n; ++i) {
    ans[i] = min(r - i + 1, ans[i - l]);
    while (ans[i] + i < n && s[ans[i]] == s[i + ans[i]]) {
      ++ans[i];
    }
    if (i + ans[i] - 1 > r) {
      l = i, r = i + ans[i] - 1;
    }
    r = max(r, i);
  }
  return ans;
}
const long double EPS = 0.000000001;
const long double INFD32 = 1000000000;
const long long INF64 = 1000000000000000000;
const long long INF32 = 1000000000;
const long long one = 1;
long long arr[1010][1010];
signed main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long k = 0;
  for (long long i = 0; i < n; i += 4) {
    for (long long j = 0; j < n; j += 4) {
      for (long long i1 = i; i1 < i + 4; ++i1) {
        for (long long j1 = j; j1 < j + 4; ++j1) {
          arr[i1][j1] = k;
          ++k;
        }
      }
    }
  }
  for (long long i = 0; i < n; ++i) {
    for (long long j = 0; j < n; ++j) cout << arr[i][j] << " ";
    cout << "\n";
  }
  return 0;
}