write a go solution for 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<=i,j<=n, ineqj)
- OR i j: ask for the bitwise OR of elements a_i and a_j (1<=i,j<=n, ineqj)
- XOR i j: ask for the bitwise XOR of elements a_i and a_j (1<=i,j<=n, ineqj)

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<=n<=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].. Output only the code with no comments, explanation, or additional text.