CF1556D.Take a Guess

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

这是一个交互式题目。

威廉心中有一个整数序列 $a_1, a_2, \dots, a_n$，但由于安全考虑，他并不想将该序列完全透露给你。威廉最多会回答 $2 \cdot n$ 个如下形式的问题：

• 下标为 $i$ 和 $j$（其中 $i \neq j$）的两个元素的按位与结果是多少？
• 下标为 $i$ 和 $j$（其中 $i \neq j$）的两个元素的按位或结果是多少？

你可以向威廉提出上述问题，你需要据此找出该序列中第 $k$ 小的数。

形式化地，第 $k$ 小的数定义为：将序列按非递减顺序排序后（下标从 1 开始），位于第 $k$ 个位置上的数。例如，在数组 $[5, 3, 3, 10, 1]$ 中，第 $4$ 小的数是 $5$，而第 $2$ 小和第 $3$ 小的数均为 $3$。

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

保证序列中每个元素均满足条件 $0 \le a_i \le 10^9$。

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)

Notes

and 2 5

2

$a_2=6$, $a_5=3$. Interactor returns bitwise AND of the given numbers.

or 5 6

7

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

在该示例中，隐藏序列为 $[1, 6, 4, 2, 3, 5, 4]$。

以下是该示例中的交互过程。

查询（选手程序）

响应（交互器）

说明

and 2 5

2

$a_2=6$，$a_5=3$。交互器返回所给两数的按位与（bitwise AND）结果。

or 5 6

7

$a_5=3$，$a_6=5$。交互器返回所给两数的按位或（bitwise OR）结果。

finish 5

$5$ 是正确答案。注意：你必须找出第 $k$ 小的数的值，而非其下标。