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+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.
Output Format:
None
Note:
The array $$$a$$$ in the example is $$$[0, 0, 2, 3]$$$.