Задача H. Матрёшки АТЭС ≡

Условие

К моменту проведения саммита АТЭС во Владивостоке было решено изготовить подарочные наборы матрёшек, по N штук в каждом.

Матрёшек в каждом наборе располагают в порядке убывания вместимости и нумеруют от 1 до N. Таким образом самая большая матрёшка получает номер 1, а самая маленькая — N. Для упаковки матрёшек в набор используют следующий алгоритм: за один шаг каждая матрёшка, находящаяся на четной позиции, помещается (вместе со всеми матрёшками внутри) внутрь ближайшей слева матрёшки. Эта операция продолжается до тех пор, пока все матрёшки не будут упакованы в одну.

После упаковки достаточно большого количества наборов обнаружилось, что оборудование, красящее матрёшки с номерами X и Y, сломалось, и в наборах оказались неокрашенные сувениры. Для быстрого извлечения матрёшек с этими номерами требуется восстановить часть шагов алгоритма упаковки, выполнявшихся до тех пор, пока одна из них не оказалась внутри другой.

i-ый шаг алгоритма описывается путём указания четырёх чисел X_Li, X_Ri, Y_Li, Y_Ri, обозначающих, что после упаковки матрёшки с номером X_Ri в матрёшку с номером X_Li, матрёшка X оказалась внутри X_Li. Аналогично для матрёшки Y.

Последний шаг алгоритма описывается двумя числами L_F, R_F — после упаковки матрёшки с номером R_F в матрёшку с номером L_F оказалось, что матрёшки X и Y находятся внутри матрёшки L_F.

Формат входного файла

Входной файл содержит три целых числа — N X Y.

Формат выходного файла

Выходной файл должен содержать подробный процесс упаковки матрёшек:

• Каждая строка, описывающая один шаг алгоритма, кроме последней, должна содержать четыре целых числа — X_Li, X_Ri, Y_Li, Y_Ri
• Последняя строчка должна содержать два целых числа — L_F, R_F

В случае, когда на каком-либо шаге в матрёшку ничего не упаковывается, указать, что матрёшка помещается сама в себя.

Ограничения

2 ≤ N ≤ 2³⁰

1 ≤ X < Y ≤ N

Примеры тестов

6 2 5

1 2  5 6
1 3  5 5
1 5

21 9 15

9 10  15 16
9 11  13 15
9 13