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

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 230

1 ≤ X < Y ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2 5
1 2  5 6
1 3  5 5
1 5
2
21 9 15
9 10  15 16
9 11  13 15
9 13

0.044s 0.009s 15