D. Змейка в кубе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Имеется куб размера n × n × n, разбитый на единичные кубики. Требуется пронумеровать все единичные кубики этого куба натуральными числами от 1 до n3 так, чтобы:

  • каждое число было использовано в качестве номера ровно один раз;
  • для каждого 1 ≤ i < n3 единичные кубики с номерами i и i + 1 были соседними (то есть имели общую грань);
  • для каждого 1 ≤ i < n нашлись хотя бы два различных подкуба размера i × i × i, составленные из единичных кубиков, которые пронумерованы последовательными числами. То есть существуют такие два числа x и y, что единичные кубики первого подкуба пронумерованы числами x, x + 1, ..., x + i3 - 1, а единичные кубики второго подкуба — числами y, y + 1, ..., y + i3 - 1.

Найдите и выведите требуемую нумерацию единичных кубиков куба.

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 50) — размер куба, единичные кубики которого нужно пронумеровать.

Выходные данные

Выведите все слои куба в виде n матриц n × n, разделяя их переводом строки. Слои надо выводить в порядке их следования в кубе. Смотрите примеры для более точного понимания.

Гарантируется, что всегда существует решение удовлетворяющее условиям задачи.

Примеры
Входные данные
3
Выходные данные
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

Примечание

В примере кубики размера 2 × 2 × 2 пронумерованы числами 1, ..., 8 и 5, ..., 12.