1556D · Take a Guess

Problem: This is an interactive task

William has a certain sequence of integers $a_1, a_2, \dots, a_n$ in his mind, but due to security concerns, he does not want to reveal it to you completely. William is ready to respond to no more than $2 \cdot n$ of the following questions:

• What is the result of a bitwise AND of two items with indices $i$ and $j$ ($i \neq j$)
• What is the result of a bitwise OR of two items with indices $i$ and $j$ ($i \neq j$)

You can ask William these questions and you need to find the $k$-th smallest number of the sequence.

Formally the $k$-th smallest number is equal to the number at the $k$-th place in a 1-indexed array sorted in non-decreasing order. For example in array $[5, 3, 3, 10, 1]$ $4$th smallest number is equal to $5$, and $2$nd and $3$rd are $3$.

Input Format: It is guaranteed that for each element in a sequence the condition $0 \le a_i \le 10^9$ is satisfied.

Note: In the example, the hidden sequence is $[1, 6, 4, 2, 3, 5, 4]$.

Below is the interaction in the example.

Query (contestant's program)Response (interactor)Notesand 2 52$a_2=6$, $a_5=3$. Interactor returns bitwise AND of the given numbers.or 5 67$a_5=3$, $a_6=5$. Interactor returns bitwise OR of the given numbers.finish 5$5$ is the correct answer. Note that you must find the value and not the index of the kth smallest number.