时空限制

1S/512M

题目描述

Z形填数是一种将 $1\sim 2^x \times 2^x$ 的数字依次填入 $2^x\times 2^x$ 的方阵的填数方法，对 $2^x\times 2^x$ 的方阵进行Z形填数的规则如下：

• 如果 $x>1$，将方阵分为四个 $2^{x-1}\times 2^{x-1}$ 的小方阵，如下图所示：

• 按红、黄、蓝、绿的先后顺序依次对四个小方阵进行Z形填数；
• 直到 $x=1$ 时，按左上、右上、左下、右下的先后顺序将数字填入 $4$ 个格子。

请输出对 $2^n\times 2^n$ 的方阵进行Z形填数的结果。

格式

输入格式

第一行包含一个整数 $n$，含义与题目描述相同。

输出格式

输出 $2^n$ 行每行 $2^n$ 个整数，表示对 $2^n\times 2^n$ 的方阵进行Z形填数的结果。

样例

样例输入 #1

3

样例输出 #1

1 2 5 6 17 18 21 22
3 4 7 8 19 20 23 24
9 10 13 14 25 26 29 30
11 12 15 16 27 28 31 32
33 34 37 38 49 50 53 54
35 36 39 40 51 52 55 56
41 42 45 46 57 58 61 62
43 44 47 48 59 60 63 64

数据规模

对于 $100\%$ 的数据，$1\leq n\leq 10$。