D. Хорошие раскраски 6
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нокотан большой фанат раскрашивания табличек. Она придумала число $$$c$$$ ($$$1 \leq c \leq 17$$$) и решила, что перед входом в здание клуба должна висеть таблица со следующими свойствами:

  1. Высота таблицы $$$h$$$ и ширина таблицы $$$w$$$ удовлетворяют ограничениям ($$$1 \leq h, w \leq 1500$$$).
  2. Каждая клетка может быть раскрашена в какое-то подмножество из $$$c$$$ цветов (возможно пустое). Формально пусть $$$a_{i, j}$$$ — число, записанное в таблице в клетке с координатами $$$i, j$$$, тогда $$$0 \leq a_{i, j} \lt 2^c$$$ и считается, что клетка покрашена в том числе в цвет с номером $$$k$$$ ($$$0 \leq k \lt c$$$), если $$$\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1$$$.
  3. Пусть $$$1 \leq x \lt 2^c$$$ и $$$cnt_x$$$ — число клеток, на которых записано число $$$x$$$. Тогда должно выполняться неравенство $$$1 \leq cnt_x \leq 20$$$.
  4. Каждый цвет образует одну компоненту связности. Формально для любого $$$0 \leq k \lt c$$$ клетки, в которых $$$k$$$-й бит записи ненулевой ($$$\lfloor \frac{a_{i,j}}{2^k} \rfloor \mod 2 = 1$$$), образуют одну компоненту связности. (Две клетки находятся в одной компоненте связности, если от одной из них можно добраться до второй, переходя в соседние четыре по горизонтали или вертикали клетки множества).

Помогите Нокотан найти таблицу, удовлетворяющую всем свойствам для заданного $$$c$$$.

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

В единственной строке входных данных содержится целое число $$$c$$$ ($$$1 \leq c \leq 17$$$) — количество цветов, в которые должна быть раскрашена таблица.

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

В первой строке выведите пару целых чисел $$$h, w$$$ ($$$1 \leq h, w \leq 1500$$$) — высота и ширина таблицы соответственно. В следующих $$$h$$$ строках выведите по $$$w$$$ целых чисел $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \lt 2^c$$$) — значения в таблице. Таблица должна удовлетворять четырем условиям, описанным в условии задачи.

Примеры
Входные данные
1
Выходные данные
1 3
1 0 0
Входные данные
2
Выходные данные
3 1
1
3
2
Входные данные
3
Выходные данные
2 6
7 7 7 7 7 7
1 2 3 4 5 6
Примечание

Во втором тестовом примере клетки, покрашенные в цвет с номером $$$0$$$, имеют координаты $$$(0, 0)$$$ и $$$(1, 0)$$$ и поэтому образуют $$$1$$$ компоненту связности. Клетки, покрашенные в цвет с номером $$$1$$$, имеют координаты $$$(1, 0)$$$ и $$$(2, 0)$$$ и поэтому также образуют $$$1$$$ компоненту связности. Несложно увидеть, что все остальные условия тоже выполнены.

В третьем тестовом примере количество клеток с каждым значением, кроме $$$0$$$ и $$$7$$$, равняется $$$1$$$. Количество клеток с $$$7$$$ равняется $$$6$$$, что подходит под интервал $$$[1, 20]$$$, и на количество клеток с $$$0$$$ в условии не накладывается ограничений. Каждый цвет образует $$$1$$$ компоненту связности, так как все клетки инцидентны к первому ряду, который связан по всем цветам.