D. Прогулка по матрице
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Боб играет в игру под названием «Прогулка по матрице»

В этой игре игроку дается $$$n \times m$$$ матрица $$$A=(a_{i,j})$$$, то есть элемент в $$$i$$$-й строке в $$$j$$$-м столбце — $$$a_{i,j}$$$. В начале игры игрок стоит на позиции $$$(1,1)$$$ со счетом $$$a_{1,1}$$$.

Чтобы достичь финиша, позиции $$$(n,m)$$$, игрок может ходить вправо или вниз, то есть из $$$(x,y)$$$ в $$$(x,y+1)$$$ или $$$(x+1,y)$$$, до тех пор, пока не выходит за пределы матрицы.

Каждый шаг, однако, изменяет счет игрока на побитовое И текущего счета и значения клетки, в которую он переходит.

Конечно же, Боб сразу решил вычислить максимальный счет, который он может набрать, с помощью недавно изученной им техники динамического программирования. Вот его алгоритм для данной задачи.

Однако, он тут же понял, что его алгоритм неправильно находит максимальный счет для некоторой матрицы $$$A$$$. Поэтому теперь он хочет для каждого неотрицательного целого числа $$$k$$$ найти такую $$$n \times m$$$ матрицу $$$A=(a_{i,j})$$$, что

  • $$$1 \le n,m \le 500$$$ (Боб ненавидит большие матрицы);
  • $$$0 \le a_{i,j} \le 3 \cdot 10^5$$$ для всех $$$1 \le i\le n,1 \le j\le m$$$ (Боб ненавидит большие числа);
  • разница между максимальным счетом, который он может набрать, и выводом алгоритма составляет ровно $$$k$$$.

Можно показать, что для любого целого $$$k$$$ такого, что $$$0 \le k \le 10^5$$$, существует матрица, удовлетворяющая данным условиям.

Помогите Бобу с этой задачей!

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

В единственной строке записано одно целое число $$$k$$$ ($$$0 \le k \le 10^5$$$).

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

В первой строке выведите два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$), обозначающие размеры матрицы.

Затем выведите $$$n$$$ строк по $$$m$$$ целых чисел в каждой строке, $$$a_{i,j}$$$ в $$$(i+1)$$$-й строке, $$$j$$$-м столбце.

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

В первом примере максимальный счет, который может набрать Боб, равен $$$300000$$$, и вывод его алгоритма тоже $$$300000$$$.

Во втором примере максимальный счет, который Боб может набрать, равен $$$7\&3\&3\&3\&7\&3=3$$$, когда вывод его алгоритма — это $$$2$$$.