A13905 | Bitwise Queries (Hard Version)

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