Очередная карточная игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У принцессы Зельды была колода из $$$n$$$ карт. На каждой карте было написано целое число от $$$1$$$ до $$$n$$$, причём изначально не было двух карт с одинаковыми числами на них. Затем она использовала силу волшебного Жезла Трифа и создала копию каждой карты.

К сожалению, карты упали на землю рубашками вверх, и теперь нужно снова собрать все карты по парам, иначе ими не получится пользоваться.

Просто перевернуть все карты было бы слишком скучно, поэтому Зельда решила выбирать по две карты и смотреть, совпали ли их значения. Если совпали, то она их откладывает в сторону, и выбирает следующую пару карт. Иначе она переворачивает эти карты обратно и выбирает пару карт заново.

Единственное, что Зельде известно изначально — если пронумеровать все лежащие на земле карточки от $$$1$$$ до $$$2n$$$, то значение на карточке под номером $$$a$$$ строго меньше, чем на карточке под номером $$$b$$$.

Несмотря на желание сделать процесс сортировки карт интересным, принцесса очень спешит, поэтому хочет закончить за не более чем $$$2n - 1$$$ ход. Помогите ей в этом!

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

В первой строке даны три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ — количество карточек, которые изначально были у Зельды, а также номера двух карточек, про значения которых известно, что первое меньше второго ($$$2 \le n \le 50\,000$$$; $$$1 \le a, b \le 2n$$$; $$$a \ne b$$$).

После считывания ввода вашей программой запускается процесс взаимодействия с интерактором.

Протокол взаимодействия

В процессе взаимодействия с интерактором ваша программа должна сообщать интерактору запросы в формате «? $$$x$$$ $$$y$$$», где $$$x$$$ и $$$y$$$ — два различных целых числа от $$$1$$$ до $$$2n$$$, обозначающие номера карточек, которые Зельда должна перевернуть на очередном ходу.

В ответ интерактор в отдельной строке напечатает через пробел два целых числа от $$$1$$$ до $$$n$$$ — значения, написанные на этих карточках. Если значения совпали, эти карточки убираются и больше не должны упоминаться в запросах.

Если какой-то из сделанных вашей программой запросов будет некорректен, интерактор выведет «-1 -1» и завершится с вердиктом WA (Wrong Answer). Также если ваша программа превысит лимит в $$$2n - 1$$$ запрос, интерактор завершится тем же образом.

Если же ваша программа сможет на $$$2n - 1$$$ запрос или меньше перевернуть все карточки по парам с одинаковыми значениями, интерактор завершится с вердиктом OK. Во избежание получения вердиктов TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded) ваша программа также должна завершаться с кодом возврата $$$0$$$ после успешного ответа интерактора на последний запрос.

Также обратите внимание, что вывод каждого запроса должен завершаться переводом строки (символ '{\}n') и сбросом буфера вывода (sys.stdout.flush() в Python, cout.flush() в C++, System.out.flush() в Java и аналогичными методами в других языках).

Примеры

Входные данные
2 1 4

1 1

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

1 3

2 4
Входные данные
3 5 3

3 2

3 3

1 2

2 2

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

3 5

3 4

1 5

2 5

1 6