Bitwise Queries (Hard Version)

**本题使用SPJ交互评测** Ridbit 有一个隐藏的长度为 $n$ 的整数数组 $a$，想让 Ashish 去猜，注意 $n$ 是 $2$ 的**整数次幂**。Ridbit 允许 Ashish 提出三种不同类型的查询。它们分别是： AND $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$and$](https://en.wikipedia.org/wiki/Bitwise_operation#AND) ($1≤i$,$j≤n$,$i≠j$) OR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$or$](https://en.wikipedia.org/wiki/Bitwise_operation#OR) ($1≤i$,$j≤n$,$i≠j$) XOR $i$ $j$: 求元素 $a_i$ 和 $a_j$ 每一位的 [$xor$](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) ($1≤i$,$j≤n$,$i≠j$) 有限制：(1) Ashish 最多可以询问 $n + 1$ 次。(2) $a$ 数组满足 $0 \le a_i \le n - 1$。 ### 输入 输入的第一行包含一个整数$n$，保证$n$在$4 \leq n \leq 2^{16}$，也就是数组的长度。同时保证$n$是$2$的整数次幂。 ### 输出 评测时，请打印一行包含以下内容之一（不带引号） - "AND i j" - "OR i j" - "XOR i j" 对于每次评测，你会得到一个$int$类型的$x$，这取决于评测数据的类型。如果查询的索引无效或超过查询数量，$x$会变成$-1$，即$x=-1$。当$x=-1$时，你应该立刻终止程序。 当计算出数组中的元素时，输出单行的"!"（英文格式，不带引号），然后输出$n$以空格分隔的整数数组的元素。 数组**并没有**对要求查询的数量计算。 **交互器不是自适应的**。数组$a$**不会**随着评测而改变。 输出后，不要忘记输出行尾并刷新输出。否则，会有`Idleness limit exceeded`报错。 使用： - C++中，使用`fflush(stdout)`或者`cout.flush()`； - Java中，使用`System.out.flush()`； - Pascal中，使用`flush(output)`； - Python中，使用`stdout.flush()`； - 其他语言中，按照其要求。 Translated by @[qinyihao](luogi.com.cn/user/348831) on 2020/11/22.

The only difference between the easy and hard versions is the constraints on the number of queries. This is an interactive problem. Ridbit has a hidden array $ a $ of $ n $ integers which he wants Ashish to guess. Note that $ n $ is a power of two. Ashish is allowed to ask three different types of queries. They are of the form - AND $ i $ $ j $ : ask for the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of elements $ a_i $ and $ a_j $ $ (1 \leq i, j \le n $ , $ i \neq j) $ - OR $ i $ $ j $ : ask for the [bitwise OR](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of elements $ a_i $ and $ a_j $ $ (1 \leq i, j \le n $ , $ i \neq j) $ - XOR $ i $ $ j $ : ask for the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of elements $ a_i $ and $ a_j $ $ (1 \leq i, j \le n $ , $ i \neq j) $ Can you help Ashish guess the elements of the array? In this version, each element takes a value in the range $ [0, n-1] $ (inclusive) and Ashish can ask no more than $ n+1 $ queries.

The first line of input contains one integer $ n $ $ (4 \le n \le 2^{16}) $ — the length of the array. It is guaranteed that $ n $ is a power of two.

To ask a query print a single line containing one of the following (without quotes) - "AND i j" - "OR i j" - "XOR i j" where $ i $ and $ j $ $ (1 \leq i, j \le n $ , $ i \neq j) $ denote the indices being queried.For each query, you will receive an integer $ x $ whose value depends on the type of query. If the indices queried are invalid or you exceed the number of queries however, you will get $ x = -1 $ . In this case, you should terminate the program immediately. When you have guessed the elements of the array, print a single line "! " (without quotes), followed by $ n $ space-separated integers — the elements of the array. Guessing the array does not count towards the number of queries asked. The interactor is not adaptive. The array $ a $ does not change with queries. After printing a query do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see the documentation for other languages. Hacks To hack the solution, use the following test format: On the first line print a single integer $ n $ $ (4 \le n \le 2^{16}) $ — the length of the array. It must be a power of 2. The next line should contain $ n $ space-separated integers in the range $ [0, n-1] $ — the array $ a $ .

4

0

2

3

OR 1 2

OR 2 3

XOR 2 4

! 0 0 2 3

The array $ a $ in the example is $ [0, 0, 2, 3] $ .