#P1451E1. Bitwise Queries (Easy Version)
-
ID: 514
Type: RemoteJudge
4000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 7
Uploaded By:
Hydro
Tags> Bitwise Queries (Easy Version)
Description
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.
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
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$.
Input
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.
Samples
4
0
2
3
OR 1 2
OR 2 3
XOR 2 4
! 0 0 2 3
Note
The array $a$ in the example is $[0, 0, 2, 3]$.