Take a Guess
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 1800
Tags: bitmasks, constructive algorithms, interactive, math

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.

Interaction format:
In the first line you will be given two integers $$$n$$$ and $$$k$$$ $$$(3 \le n \le 10^4, 1 \le k \le n)$$$, which are the number of items in the sequence $$$a$$$ and the number $$$k$$$.

After that, you can ask no more than $$$2 \cdot n$$$ questions (not including the "finish" operation).

Each line of your output may be of one of the following types:

- "or i j" $$$(1 \le i, j \le n, i \neq j)$$$, where $$$i$$$ and $$$j$$$ are indices of items for which you want to calculate the bitwise OR.
- "and i j" $$$(1 \le i, j \le n, i \neq j)$$$, where $$$i$$$ and $$$j$$$ are indices of items for which you want to calculate the bitwise AND.
- "finish res", where $$$res$$$ is the $$$k$$$th smallest number in the sequence. After outputting this line the program execution must conclude.

In response to the first two types of queries, you will get an integer $$$x$$$, the result of the operation for the numbers you have selected.

After outputting a line do not forget to output a new line character and flush the output buffer. Otherwise you will get the "Idleness limit exceeded". To flush the buffer use:

- fflush(stdout) in C++
- System.out.flush() in Java
- stdout.flush() in Python
- flush(output) in Pascal
- for other languages refer to documentation

If you perform an incorrect query the response will be $$$-1$$$. After receiving response $$$-1$$$ you must immediately halt your program in order to receive an "Incorrect answer" verdict.

Hacking

To perform a hack you will need to use the following format:

The first line must contain two integers $$$n$$$ and $$$k$$$ $$$(3 \le n \le 10^4, 1 \le k \le n)$$$, which are the number of items in the sequence $$$a$$$ and the number $$$k$$$.

The second line must contain $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$, the sequence $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
7 6

2

7

Example output:
and 2 5

or 5 6

finish 5

Editorial:
To solve this problem, we can use the fact that $$$a+b=(a$$$ or $$$b) + (a$$$ and $$$b)$$$.
Then we can determine the first $$$3$$$ numbers in $$$6$$$ operations using the sums $$$a_{01} = a_0 + a_1$$$, $$$a_{12} = a_1 + a_2$$$ and $$$a_{02} = a_0 + a_2$$$. Using the formula $$$a_1 = \frac{a_{01}+a_{12}-a_{02}}{2}$$$, $$$a_0 = a_{01} - a_1$$$ and $$$a_2 = a_{12} - a_1$$$.
Knowing one of the numbers, it is quite simple to find all the other numbers using the same principle by using $$$2 \cdot n$$$ operations. Then we just need to sort the resulting array and output the k-th element.