Cube Snake

You've got an n × n × n cube, split into unit cubes. Your task is to number all unit cubes in this cube with positive integers from 1 to n3 so that:

• each number was used as a cube's number exactly once;
• for each 1 ≤ i < n3, unit cubes with numbers i and i + 1 were neighbouring (that is, shared a side);
• for each 1 ≤ i < n there were at least two different subcubes with sizes i × i × i, made from unit cubes, which are numbered with consecutive numbers. That is, there are such two numbers x and y, that the unit cubes of the first subcube are numbered by numbers x, x + 1, ..., x + i3 - 1, and the unit cubes of the second subcube are numbered by numbers y, y + 1, ..., y + i3 - 1.

Find and print the required numeration of unit cubes of the cube.

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the cube, whose unit cubes need to be numbered.

Output

Print all layers of the cube as n n × n matrices. Separate them with new lines. Print the layers in the order in which they follow in the cube. See the samples for clarifications.

It is guaranteed that there always is a solution that meets the conditions given in the problem statement.

Examples

Input

3

Output

1 4 17 2 3 18 27 26 19

8 5 16 7 6 15 24 25 20

9 12 13 10 11 14 23 22 21

Note

In the sample the cubes with sizes 2 × 2 × 2 are numbered with integers 1, ..., 8 and 5, ..., 12.

inputFormat

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the cube, whose unit cubes need to be numbered.

outputFormat

Output

Print all layers of the cube as n n × n matrices. Separate them with new lines. Print the layers in the order in which they follow in the cube. See the samples for clarifications.

It is guaranteed that there always is a solution that meets the conditions given in the problem statement.

Examples

Input

3

Output

1 4 17 2 3 18 27 26 19

8 5 16 7 6 15 24 25 20

9 12 13 10 11 14 23 22 21

Note

In the sample the cubes with sizes 2 × 2 × 2 are numbered with integers 1, ..., 8 and 5, ..., 12.

样例

3

1 8 9
2 7 10
27 26 25
4 5 12
3 6 11
22 23 24
15 14 13
16 17 18
21 20 19

</p>