정사각형 모양의 미로에 있는 모든 방에 번호를 붙이려고 한다. 미로는 \(N\)개의 행과 \(N\)개의 열로 이루어져 있으며, 번호는 0부터 차례대로 붙인다.

하나의 정사각형 구역을 처리하는 방법은 다음과 같다.

• 구역이 방 한 칸으로 이루어져 있다면, 그 방에 아직 사용하지 않은 가장 작은 번호를 붙인다.
• 구역의 한 변의 길이가 2 이상이라면 구역을 크기가 같은 네 개의 정사각형으로 나누고, 다음 순서대로 처리한다.
  1. 왼쪽 위 구역
  2. 왼쪽 아래 구역
  3. 오른쪽 아래 구역
  4. 오른쪽 위 구역

각각의 작은 구역도 같은 규칙에 따라 재귀적으로 처리한다. 즉, 왼쪽 위에서 시작하여 네 구역을 반시계 방향으로 처리한다.

다음 그림은 네 구역을 처리하는 순서를 나타낸다.

\(N=4\)일 때 모든 방에 번호를 붙인 결과는 다음과 같다. 같은 배경색은 처음 나눈 네 구역 가운데 하나를 나타낸다.

미로의 크기 \(N\)이 주어졌을 때, 모든 방에 번호를 붙인 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 한 변의 길이 \(N\)이 주어진다.

출력

\(N\)개의 줄에 걸쳐 번호를 모두 붙인 미로를 출력한다.

각 줄에는 해당 행에 있는 \(N\)개의 정수를 공백으로 구분하여 출력한다.

제한 사항

• \(N=2^k\)이다.
• \(0 \le k \le 6\)
• 따라서 \(1 \le N \le 64\)이다.

예제 입력 1

2

예제 출력 1

0 3
1 2

예제 설명 1

각 구역이 한 칸이므로 왼쪽 위, 왼쪽 아래, 오른쪽 아래, 오른쪽 위 순서로 0부터 3까지의 번호를 붙인다.

예제 입력 2

4

예제 출력 2

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

예제 설명 2

먼저 전체 미로를 네 구역으로 나누어 왼쪽 위, 왼쪽 아래, 오른쪽 아래, 오른쪽 위 순서로 처리한다. 각 구역 내부에서도 같은 규칙을 적용하면 그림과 같은 결과가 만들어진다.