Это интерактивная задача.

На кафедре сверхъестественных явлений Оксенфуртской Академии открылась Библиотека Магии, в которую вошли труды величайших чародеев Редании — $$$n$$$ ($$$3 \leq n \leq 10^{18}$$$) видов книг, пронумерованных от $$$1$$$ до $$$n$$$. У каждой книги номер вида обозначен на переплёте. Более того, книги каждого вида хранятся в библиотеке ровно в двух экземплярах! А библиотекарем назначили Вас.

Однажды ночью Вы просыпаетесь от странного шума и видите существо, покидающее здание через окно. Из рюкзака таинственного вора торчали три толстых тома разных цветов. И перед тем как приступить к их поиску, Вы решили вычислить числа $$$a$$$, $$$b$$$ и $$$c$$$, написанные на переплётах этих книг. Все три числа различны.

Итак, в Вашем распоряжении неупорядоченное множество томов, в котором по одному тому с попарно различными числами $$$a$$$, $$$b$$$ и $$$c$$$ и по два тома для всех чисел от $$$1$$$ до $$$n$$$, кроме $$$a$$$, $$$b$$$ и $$$c$$$. И Вы хотите найти эти значения $$$a$$$, $$$b$$$ и $$$c$$$.

Так как Вы работаете не в простой библиотеке, а в Библиотеке Магии, то для проверки факта нахождения книг на своём месте Вы можете использовать только одно заклинание в виде запроса:

• «xor l r» — Запрос побитового XOR-а с параметрами $$$l$$$ и $$$r$$$. Пусть $$$k$$$ — количество таких томов в библиотеке, числа на которых больше либо равны $$$l$$$ и меньше либо равны $$$r$$$. Вы получите результат вычисления $$$v_1 \oplus v_2 \oplus ... \oplus v_k$$$, где $$$v_1 ... v_k$$$ — числа на переплётах этих томов, а $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Так как Ваши магические способности как библиотекаря сильно ограничены, Вы можете сделать не более $$$150$$$ запросов.

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Затем вы можете сделать до $$$150$$$ запросов.

Чтобы сделать запрос, выведите строку в формате «xor l r» (без кавычек) ($$$1 \leq l \leq r \leq n$$$). После каждого запроса считайте целое число — ответ на ваш запрос.

Чтобы сообщить ответ, выведите строку в формате «ans a b c» (без кавычек), где $$$a$$$, $$$b$$$ и $$$c$$$ — найденные вами числа для ответа на задачу. Вы можете вывести их в любом порядке.

Интерактор не адаптивен, что означает, что ответ известен до того, как участник задаст запросы, и не зависит от запросов, заданных участником.

После того как будет сделано $$$150$$$ запросов, ответ на любой другой запрос будет равен $$$-1$$$. Получив такой ответ, завершите программу, чтобы получить вердикт «WA» (Wrong answer).

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт «IL» (Idleness limit exceeded). Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы

Чтобы сделать взлом, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 300$$$) — количество наборов входных данных.

Единственная строка каждого набора должна содержать четыре целых числа $$$n$$$, $$$a$$$, $$$b$$$ и $$$c$$$ ($$$3 \leq n \leq 10^{18}$$$, $$$1 \le a, b, c \le n$$$) — количество книг в библиотеке и номера украденных томов. Числа $$$a$$$, $$$b$$$ и $$$c$$$ должны быть различными.