Это задача с выводом только ответов (output-only). Обратите внимание, что вам всё равно нужно отправить код, который выводит результат, а не текстовый файл.

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

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

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

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

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

Для этой задачи нет входных данных.

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

Сначала выведите $n$ и $m$ ($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$) — количество вершин и ребер исходного графа (построенного заранее). Затем выведите $m$ строк вида $(u, v)$ — ребра графа.

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

Выведите $e$ — количество ребер, которые вы добавите для данного $k$ ($1 \le e \le 17$). Затем выведите $e$ строк вида $(u, v)$ — ребра, которые вы добавите в свой граф.

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

Примеры

Пример 1

3 2
1 2
2 3
1
1 3
0

Примечание

Пример вывода приведен для иллюстрации. Он содержит вывод для $k = 1, 2$.