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

简单版本与困难版本的唯一区别在于查询次数的限制。

这是一道交互式题目。

Ridbit 有一个长度为 $n$ 的隐藏数组 $a$（其中每个元素均为整数），他希望 Ashish 猜出该数组。注意，$n$ 是 $2$ 的幂次。Ashish 可以提出三种不同类型的查询，形式如下：

• AND i j：询问元素 $a_i$ 与 $a_j$ 的按位与结果（其中 $1 \leq i, j \le n$，且 $i \neq j$）；
• OR i j：询问元素 $a_i$ 与 $a_j$ 的按位或结果（其中 $1 \leq i, j \le n$，且 $i \neq j$）；
• XOR i j：询问元素 $a_i$ 与 $a_j$ 的按位异或结果（其中 $1 \leq i, j \le n$，且 $i \neq j$）。

你能否帮助 Ashish 推断出数组的所有元素？

在本版本中，每个元素的取值范围为 $[0, n-1]$（含端点），且 Ashish 最多只能进行 $n+1$ 次查询。

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.

输入的第一行包含一个整数 $n$ $(4 \le n \le 2^{16})$ —— 数组的长度。保证 $n$ 是 $2$ 的幂。

The array $a$ in the example is $[0, 0, 2, 3]$.

示例中的数组 $a$ 为 $[0, 0, 2, 3]$。