TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

89.7% (26/29)

Submission's AC Ratio

34.8% (40/115)

Description

在大陸人把冰塊排進他$2^ N\times 2^ N$的盒子之後,他決定把每顆在盒子裡的冰塊都做個編號,從0編號到$2^ {2N}-1$。

然而,身為全世界唯一地大陸人,他不想像普通人一樣老老實實的從上到下、從左到右,或是用S型的方式把冰塊編號。他還希望,編號相鄰的冰塊在冰塊盒上也要相鄰,以方便他找冰塊。

在思考該怎麼將他的冰塊編號的時候,他看著他$2\times 2$的迷你冰塊盒,腦袋浮現了一個靈感。
他在冰塊盒上畫出了這樣的一條線:

從左上到右上,他決定幫冰塊按照這條線經過的順序編號。

決定了這個小盒子的編號順序之後,他拿了四個畫好線的$2\times 2$的冰塊盒,再拼成大一點的$4\times 4$冰塊盒。這時,他發現:只要把左上方的$2\times 2$冰塊盒逆時針轉90度、右上方的$2\times 2$冰塊盒順時針轉90度,下面兩個$2\times 2$方向保持不變,再按照原本$2\times 2$的順序(左上、左下、右下、右上)把線全部串起來,那麼編號就連續了!如下圖:

更棒的是,既然$2\times 2$的編號可以變成$4\times 4$的編號,那麼表示他$2^ N\times 2^ N$的盒子就可以透過不斷模仿這個加倍的規律編號了!

然而,因為大陸人很懶,所以他決定要你幫他把冰塊的編號算出來。

Input Format

輸入只有一個非負整數N,代表冰塊盒的大小是2N

子任務(測資)額外限制分數
1 (0~1)$N\leq1$11
2 (0~3)$N\leq 3$35
3 (0~6)$N\leq 6$25
4 (0~11)$N\leq 11$29

Output Format

請輸出 2N 行,每行 2N 個數字,代表大陸人對每顆冰塊的編號。

Sample Input

2

Sample Output

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

Hints

Problem Source

Problem Set by Yihda Yol / edisonhello
建國中學106學年度校隊選拔:初試pC

Subtasks

For Testdata: 0 ~ 1, Score: 11
For Testdata: 0 ~ 3, Score: 35
For Testdata: 0 ~ 6, Score: 25
For Testdata: 0 ~ 11, Score: 29
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 1000 131072 65536
2 1000 131072 65536
3 1000 131072 65536
4 1000 131072 65536
5 1000 131072 65536
6 1000 131072 65536
7 1000 131072 65536
8 1000 131072 65536
9 1000 131072 65536
10 1000 131072 65536
11 1000 131072 65536