codeforces#P1556D. Take a Guess

Take a Guess

Description

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

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

Interaction

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

Input

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

Samples

7 6

2

7
and 2 5

or 5 6

finish 5

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