Bitwise Queries (Hard Version)
Contest: Codeforces Round 685 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, constructive algorithms, interactive, math

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 of elements $$$a_i$$$ and $$$a_j$$$ $$$(1 \leq i, j \le n$$$, $$$i \neq j)$$$
- OR $$$i$$$ $$$j$$$: ask for the bitwise 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 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.

Input format:
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.

Interaction format:
To ask a query print a single line containing one of the following (without quotes)

- "AND i j"
- "OR i j"
- "XOR i j"

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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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

Example input:
4

0

2

3

Example output:
OR 1 2

OR 2 3

XOR 2 4

! 0 0 2 3

Editorial:
Key Idea:
Query the $$$n - 1$$$ xor values of the form $$$(1, i)$$$, for $$$2 \leq i \leq n$$$ initially.
Since numbers lie in the range $$$[0, n - 1]$$$, one of two cases can arise:
1. There exists indices j, k such that $$$a_{j} = a_{k}$$$. This can be found as $$$a_{i}$$$ $$$\oplus$$$ $$$a_{j}$$$ $$$=$$$ $$$a_{i}$$$ $$$\oplus$$$ $$$a_{k}$$$. So we can just use the query $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ to get the value of $$$a_{j}$$$. Now we can find the remaining values using the xor values previous queried in$$$ (n - 1) + 1 = n$$$ queries.
2. All integers in the range $$$[0, n - 1]$$$ are present. There exists (several) pairs $$$j, k$$$ such that $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ $$$=$$$ $$$n - 1$$$. This implies that neither of the numbers have any bits in common and as such $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ $$$=$$$ $$$0$$$, allowing us to save one query compared to E1. Thus we need $$$(n - 1) + 3 - 1 = (n + 1)$$$ queries.
Solution:
Now we have to eliminate $$$1$$$ more query but we are yet to use the info that all values of a are in the range $$$[0, n - 1]$$$.
It may be tempting to try to remove a xor query, but it is unlikely this will work, as we would not be able differentiate between two arrays which are equal in $$$n - 1$$$ places and differ in the position we didn't check. As such it doesn't seem probable that we can recover the exact value if we don't use $$$n - 1$$$ xor operations.
Since we'll need them anyway, lets go ahead and find $$$a_{1}$$$ $$$\oplus$$$ $$$a_{i}$$$ for all $$$2 \leq i \leq n$$$.
Then clearly we have to eliminate $$$1$$$ of the $$$3$$$ AND queries.
Since numbers lie in the range $$$[0, n - 1]$$$, one of two cases must arise:
1. At least one value is repeated. Clearly if $$$a_{1}$$$ $$$\oplus$$$ $$$a_{j} = a_{1}$$$ $$$\oplus$$$ $$$a_{k}$$$, then $$$a_{j} = a_{k}$$$. So we can use the already queried xor values to check if there exists two such values. Its easy to see that $$$x$$$ $$$\&$$$ $$$x$$$ is $$$x$$$ itself, so we can get the value of $$$a_{j}$$$ using the query $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$. Now we can just the xor values to find the remaining values. This needs $$$(n - 1) + 1 = n$$$ queries.
2. All integers in the range $$$[0, n - 1]$$$ are present.   We're trying to find a pair of values $$$(a_{j}, a_{k})$$$ for which we can find $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ without needing to query it. However we don't have any equal pair like the last case.  The next easiest value that comes to mind would be $$$0$$$. Can we easily select a pair with AND value zero based on just the info we currently have? Well if the $$$i$$$-th bit of $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ is on, then it must undoubtedly have been on in either $$$a_{j}$$$ or $$$a_{k}$$$, not both. But we can't make any such statements about a bit being off, since the bit could be off in both (satisfying the condition), or on in both (doesn't satisfy nonzero AND).  So can we choose a pair $$$(a_{j}, a_{k})$$$ such that all bits are on? Yes we can, this value will be $$$n - 1$$$ since $$$n$$$ is a power of $$$2$$$ and there will be $$$\frac{n}{2}$$$ pairs which equal it ($$$(0, n - 1)$$$, $$$(1, n - 2)$$$, $$$(2, n - 3)$$$, etc). So we can just find any one pair such that $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ $$$=$$$ $$$n - 1$$$.  Now we know $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ $$$=$$$ $$$0$$$ and can reduce the number of required AND queries by $$$1$$$. So we will need $$$(n - 1) + 3 - 1 = (n + 1)$$$ queries.
3. We're trying to find a pair of values $$$(a_{j}, a_{k})$$$ for which we can find $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ without needing to query it. However we don't have any equal pair like the last case.
4. The next easiest value that comes to mind would be $$$0$$$. Can we easily select a pair with AND value zero based on just the info we currently have? Well if the $$$i$$$-th bit of $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ is on, then it must undoubtedly have been on in either $$$a_{j}$$$ or $$$a_{k}$$$, not both. But we can't make any such statements about a bit being off, since the bit could be off in both (satisfying the condition), or on in both (doesn't satisfy nonzero AND).
5. So can we choose a pair $$$(a_{j}, a_{k})$$$ such that all bits are on? Yes we can, this value will be $$$n - 1$$$ since $$$n$$$ is a power of $$$2$$$ and there will be $$$\frac{n}{2}$$$ pairs which equal it ($$$(0, n - 1)$$$, $$$(1, n - 2)$$$, $$$(2, n - 3)$$$, etc). So we can just find any one pair such that $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ $$$=$$$ $$$n - 1$$$.
6. Now we know $$$a_{j}$$$ $$$\&$$$ $$$a_{k}$$$ $$$=$$$ $$$0$$$ and can reduce the number of required AND queries by $$$1$$$. So we will need $$$(n - 1) + 3 - 1 = (n + 1)$$$ queries.
It is easy to see that these two cases cover all situations possible and in both cases we can find the answer in at max $$$(n + 1)$$$ queries which is enough to get AC.