Это усложненная версия задачи. Две версии отличаются ограничением на число запросов. Вы можете взламывать по этой задаче только если обе версии решены.

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

У Ridbit есть массив $$$a$$$ из $$$n$$$ целых хочет, и он хочет, чтобы Ashish его отгадал. $$$n$$$ является степенью двойки. Ashish может спрашивать запросы трех видов. Они могут быть вида

• AND $$$i$$$ $$$j$$$  — узнать побитовое И элементов $$$a_i$$$ и $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$
• OR $$$i$$$ $$$j$$$  — узнать побитовое ИЛИ элементов $$$a_i$$$ и $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$
• XOR $$$i$$$ $$$j$$$  — узнать побитовое исключающее ИЛИ элементов $$$a_i$$$ и $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$

Можете ли вы помочь Ashish определить элементы массива?

В этой версии, каждый элемент имеет значение из отрезка $$$[0, n-1]$$$ (включительно) и Ashish может спросить не более $$$n+1$$$ запросов.

Чтобы сделать запрос, выведите одну из следующих строк (без кавычек):

• «AND i j»;
• «OR i j»;
• «XOR i j»;

На каждый запрос вы получите в ответ одно целое число $$$x$$$, которое означает значение ответа на ваш вопрос. Если ваш запрос некорректный, вы получите в ответ $$$x = -1$$$. В таком случае вам требуется закончить выполнение программы.

Когда вы угадали элементы массива, вам требуется вывести одну строку, содержащую «!» (без кавычек), после чего должны идти $$$n$$$ разделенных пробелами целых чисел — элементы массива.

Отгадывание массива не считается в числе сделанных запросов.

Интерактор не является адаптивным. Массив $$$a$$$ не меняется с запросами.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

Взломы

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

В первой строке выведите одно целое число $$$n$$$ $$$(4 \le n \le 2^{16})$$$ — длину массива. Она должна быть степенью двойки. В следующий строке должны быть записаны $$$n$$$ разделенных пробелами целых чисел из отрезка $$$[0, n-1]$$$ — массив $$$a$$$.