Bitwise Queries (Easy Version)
Contest: Codeforces Round 685 (Div. 2)
Difficulty rating: 2000
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+2$$$ 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:
$$$a + b = (a \oplus b) + 2 * (a \& b)$$$
Pick and distinct $$$i, j, k$$$ and find $$$a_{i} + a_{j} = x$$$, $$$a_{i} + a_{k} = y$$$ and $$$a_{j} + a_{k} = z$$$ by querying their XOR and AND values ($$$6$$$ queries). This is a system of linear equation with three equations and three variables and thus us a unique solution.
Solving it you get the values of $$$a_{i}$$$, $$$a_{j}$$$, and $$$a_{k}$$$. You can then get the remaining $$$n - 3$$$ values using $$$n - 3$$$ more queries. This uses a total of $$$n + 3$$$ queries. Realize that $$$a_{j}$$$ $$$\oplus$$$ $$$a_{k}$$$ $$$=$$$ ($$$a_{i}$$$ $$$\oplus$$$ $$$a_{j}$$$) $$$\oplus$$$ ($$$a_{i}$$$ $$$\oplus$$$ $$$a_{k}$$$) to reduce the number of initial queries from $$$6$$$ to $$$5$$$, for a total of $$$n + 2$$$ queries.
Solution:
Lets take a look at the properties of the 3 operations we have, specifically what information we can recover from it.
• AND - lossy in information about bits that are on, cant be used to recover the values
• OR - lossy in information about bits that are off, cant be used to recover the values
• XOR - lossless, a $$$\oplus$$$ (a $$$\oplus$$$ b) gives us b again.
So clearly xor operations are going to be the core of recovering the values. If we can find one of the values, we can find the remaining $$$n - 1$$$ values using xor queries.
But how do we get that first value?
Lets try to think about this for a operation for which we know how to obtain the individual values - addition. If we had $$$a + b = x$$$, $$$a + c = y$$$ and $$$b + c = z$$$, we could just solve the three linear equations to obtain the answer.
So what's the difference between xor and addition anyway?
• If the $$$i$$$-th bit is off in both the numbers, xor and addition both give 0.
• If the $$$i$$$-th bit is on in exactly oneof the numbers, xor and addition will both give $$$2^{i}$$$ .
• But what about if the $$$i$$$-th bit is on in the both the numbers? Then addition contributes $$$2 * 2^{i}$$$ to the answer while xor contributes 0.
Is there some way to recover this value? Well if $$$i$$$-th bit is on in the both the numbers, the AND will contribute $$$2^{i}$$$ to the answer. So we can realize that $$$a + b$$$ can be rewritten as (a $$$\oplus$$$ $$$b$$$) + $$$2 \times$$$ (a $$$\&$$$ b).
So now if we just choose positions $$$1$$$, $$$2$$$ and $$$3$$$, we can obtain $$$x = a_{1} + a_{2}$$$, $$$y = a_{1} + a_{3}$$$ and $$$z = a_{2} + a_{3}$$$ using $$$3$$$ XOR and $$$3$$$ AND operations. Furthermore we can realize that $$$a_{2}$$$ $$$\oplus$$$ $$$a_{3}$$$ is just ($$$a_{1}$$$ $$$\oplus$$$ $$$a_{2}$$$) $$$\oplus$$$ ($$$a_{1}$$$ $$$\oplus$$$ $$$a_{3}$$$), so we can save one more operation.
Now solving the above simultaneous equations, we get $$$a_{1}$$$ = $$$\frac{x + y - z}{2}$$$. Now for $$$2 \leq i \leq n$$$, $$$a_{i}$$$ is just $$$a_{1}$$$ $$$\oplus$$$ ($$$a_{1}$$$ $$$\oplus$$$ $$$a_{i}$$$). We already calculated $$$a_{1}$$$ $$$\oplus$$$ $$$a_{2}$$$ and $$$a_{1}$$$ $$$\oplus$$$ $$$a_{3}$$$ for the previous step, and can calculate the remaining xor values in $$$n - 3$$$ steps.
So in total we use exactly $$$5 + (n - 3)$$$ = $$$n + 2$$$ queries, which is enough to get AC.