Ваша задача — выбрать $N$ точек на координатной плоскости и провести между ними $M$ прямолинейных отрезков так, чтобы образовалось ровно $K$ конечных граней. Здесь грани — это области, на которые плоскость делится отрезками. Одна из областей является бесконечной, её следует игнорировать.

Более формально, ваша конфигурация должна удовлетворять следующим условиям:

• Координаты $x$ и $y$ каждой точки должны быть целыми числами от 1 до 79.
• Все точки должны находиться в разных позициях.
• Не должно быть нескольких отрезков, соединяющих две одни и те же точки.
• Два различных отрезка не должны пересекаться, за исключением случаев, когда они имеют общую конечную точку.
• Точки, отличные от конечных точек отрезка, не должны лежать на этом отрезке.

На рисунке ниже (a) — случай, в котором одна грань создана 3 точками и 3 отрезками. (b) — случай, в котором 3 грани созданы 4 точками и 6 отрезками. (c) — некорректный вывод, так как присутствуют кривые, а (d) — некорректный, так как есть пересекающиеся отрезки.

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

В первой строке содержатся три целых положительных числа $N$, $M$ и $K$, представляющие количество точек, количество отрезков и количество граней, которые необходимо создать, соответственно ($3 \le N \le 3000$, $0 \le M$, $0 \le K$).

Гарантируется, что для заданных $N$, $M$ и $K$ решение существует.

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

В первых $N$ строках выведите координаты выбранных точек. $i$-я из этих строк должна содержать два целых числа $x_i$ и $y_i$ ($1 \le x_i, y_i \le 79$): координаты $i$-й точки.

Затем выведите $M$ строк, описывающих отрезки. Каждая из этих строк должна содержать два целых числа от 1 до $N$: индексы точек, соединенных отрезком.

Если существует более одного возможного решения, выведите любое из них.

Примеры

Пример 1

4 6 3

1 1
3 1
2 2
2 3
1 2
1 3
1 4
2 3
2 4
3 4

Пример 2

6 5 1

1 1
1 2
2 1
3 1
3 2
4 1
1 2
1 3
2 3
4 5
5 6

Примечание

На левом рисунке показаны 3 грани, образованные 4 точками и 6 отрезками. На правом рисунке показана 1 грань, образованная 6 точками и 5 отрезками.