Это интерактивная задача.
На кафедре сверхъестественных явлений Оксенфуртской Академии открылась Библиотека Магии, в которую вошли труды величайших чародеев Редании — \(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\) должны быть различными.
Примечание
В примере в первом наборе входных данных книги в библиотеке после пропажи выглядят вот так:
Теперь рассмотрим ответы на запросы:
- На запрос «xor 1 1» вы получаете результат \(1 \oplus 1 = 0\). Указанному в запросе условию удовлетворяет два тома — оба с номером \(1\).
- На запрос «xor 2 2» вы получаете результат \(2\), так как только один том удовлетворяет указанному условию.
- На запрос «xor 3 3» вы получаете результат \(3\).
- На запрос «xor 4 6» вы получаете результат \(4 \oplus 6 \oplus 4 \oplus 5 \oplus 6 = 5\).
Во втором наборе входных данных всего \(3\) вида книг, и нетрудно догадаться, что отсутствующие имеют номера \(1\), \(2\) и \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6
0
2
3
5
3
|
xor 1 1
xor 2 2
xor 3 3
xor 4 6
ans 2 3 5
ans 1 2 3
|