Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E2. Bitwise Queries (Hard Version)

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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

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

Example

Input

4 0 2 3

Output

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2021 03:13:45 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|