1451E1 · Bitwise Queries (Easy Version)

Problem: 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.

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.

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