В этой задаче нет входных данных. Обратите внимание, что Вам следует отправить код, который печатает вывод, а не текстовый файл.

Допустимая 3-раскраска графа - это присвоение цветов (чисел) из набора {1, 2, 3} каждой из n вершин таким образом, что для любого ребра (a, b) графа вершины a и b имеют другой цвет. Таких раскрасок для графа с n вершинами не более 3n.

Вы работаете в компании, стремясь стать специалистом по созданию графов с заданным количеством 3-раскрасок. Однажды Вы узнаете, что вечером получите заказ на изготовление графа ровно с 6k 3-раскрасками. Вы не знаете точное значение k, только то что 1 ≤ k ≤ 500.

Вы не хотите ждать конкретного значения k чтобы начать строить граф. Вы заранее строите граф, содержащий не более 19 вершин. Затем, изучив конкретное значение k, Вы можете добавить не более 17 ребер, чтобы получить требуемый граф с ровно 6k 3-раскрасками.

Сможете ли Вы сделать это?

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

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

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

Сначала выведите n и m (1 ≤ n ≤ 19, 1 ≤ m ≤ n * (n - 1) / 2) - количество вершин и ребер исходного графа (построенного заранее). Затем выведите m строк в виде (u, v) - ребра графа.

Затем для каждого k от 1 до 500 выполните следующие действия:

Выведите e - количество ребер, которое Вы добавите для этого конкретного k (1 ≤ e ≤ 17). Затем выведите e строк в виде (u, v) - ребра, которые будут добавлены в граф.

В графе не должно быть петель, и для каждого k все m + e ребер, которые Вы используете, должны быть попарно различными. Количество 3-х раскрасок графика для конкретного k должно быть ровно 6k.

Пример

В примере показан ответ для k = 1, 2.