D. Попробуй угадай
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Василий загадал некоторую последовательность чисел $$$a_1, a_2, \dots, a_n$$$, но в целях безопасности он не хочет раскрывать вам ее полностью. Василий готов ответить не больше, чем на $$$2 \cdot n$$$ следующих вопросов:

  • Чему равно значение побитового И двух элементов с индексами $$$i$$$ и $$$j$$$ ($$$i \neq j$$$)
  • Чему равно значение побитового ИЛИ двух элементов с индексами $$$i$$$ и $$$j$$$ ($$$i \neq j$$$)

Вы можете задать любые интересующие вас вопросы Василию и должны узнать $$$k$$$-е наименьшее число последовательности.

Формально $$$k$$$-е наименьшее число равно числу на $$$k$$$-й позиции в отсортированном по неубыванию массиве с 1-индексацией. Для примера, в массиве $$$[5, 3, 3, 10, 1]$$$ $$$4$$$-е наименьшее число будет равно $$$5$$$, а $$$2$$$-е и $$$3$$$-е равны $$$3$$$.

Входные данные

Гарантируется, что для каждого элемента из загаданной последовательности выполняется $$$0 \le a_i \le 10^9$$$.

Протокол взаимодействия

В первой строке вам будет дано два целых числа $$$n$$$ и $$$k$$$ $$$(3 \le n \le 10^4, 1 \le k \le n)$$$ — количество элементов последовательности $$$a$$$ и число $$$k$$$.

Затем вы можете задать не более $$$2 \cdot n$$$ вопросов (операция «finish» за вопрос не считается).

Каждая строка вашего вывода может быть одного из следующих типов:

  • «or i j» $$$(1 \le i, j \le n, i \neq j)$$$, где $$$i$$$ и $$$j$$$ — это индексы элементов, побитовый or которых вы хотите узнать.
  • «and i j» $$$(1 \le i, j \le n, i \neq j)$$$, где $$$i$$$ и $$$j$$$ — это индексы элементов, побитовый and которых вы хотите узнать.
  • «finish res», где $$$res$$$ — это $$$k$$$-е наименьшее число в последовательности. После вывода такой строки необходимо завершить программу.

В ответ на первые два типа операций вы получите целое число $$$x$$$ — результат интересующей вас операции для выбранных чисел.

После вывода каждой строки не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт «Решение зависло». Для сброса буфера используйте:

  • fflush(stdout) в языке C++
  • System.out.flush() в Java
  • stdout.flush() в Python
  • flush(output) в Pascal
  • смотрите документацию для других языков

Если вы сделаете некорректный запрос, то в ответ вы получите $$$-1$$$. После получения ответа $$$-1$$$, вы должны немедленно завершить свою программу, чтобы получить вердикт «Неправильный ответ».

Взломы

Чтобы совершить взлом, вам потребуется использовать следующий формат:

Первая строка должна содержать два целых числа $$$n$$$ и $$$k$$$ $$$(3 \le n \le 10^4, 1 \le k \le n)$$$ — количество элементов последовательности $$$a$$$ и число $$$k$$$.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — описание последовательностии $$$a$$$.

Пример
Входные данные
7 6

2

7
Выходные данные
and 2 5

or 5 6

finish 5
Примечание

В тестовом примере загаданная последовательность выглядит следующим образом: $$$[1, 6, 4, 2, 3, 5, 4]$$$.

Ниже разобран протокол взаимодействия из примера.

Запрос (программа участника)Ответ (интерактор)Пояснение
and 2 52$$$a_2=6$$$, $$$a_5=3$$$. Интерактор возвращает побитовый И данных чисел.
or 5 67$$$a_5=3$$$, $$$a_6=5$$$. Интерактор возвращает побитовый ИЛИ данных чисел.
finish 5$$$5$$$ является правильным ответом. Обратите внимание, что требуется найти значение, а не индекс k-го наименьшего числа.