Это интерактивная задача.
Василий загадал некоторую последовательность чисел \(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\).
Протокол взаимодействия
В первой строке вам будет дано два целых числа \(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\).
Примечание
В тестовом примере загаданная последовательность выглядит следующим образом: \([1, 6, 4, 2, 3, 5, 4]\).
Ниже разобран протокол взаимодействия из примера.
| Запрос (программа участника) | Ответ (интерактор) | Пояснение |
| and 2 5 | 2 | \(a_2=6\), \(a_5=3\). Интерактор возвращает побитовый И данных чисел. |
| or 5 6 | 7 | \(a_5=3\), \(a_6=5\). Интерактор возвращает побитовый ИЛИ данных чисел. |
| finish 5 | | \(5\) является правильным ответом. Обратите внимание, что требуется найти значение, а не индекс k-го наименьшего числа. |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 6
2
7
|
and 2 5
or 5 6
finish 5
|