E. lce4113 и игра в охрану
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Кроме того, взломы для этой задачи отключены.

Есть два скрытых целых числа $$$b$$$ и $$$v$$$ такие, что $$$b \in \{0,1\}$$$ и $$$0 \le v \lt 2^{30}.$$$ Также есть скрытая операция $$$\mathrm{ty},$$$ которая является либо $$$\&$$$, либо $$$|.$$$ Здесь, $$$\&$$$ обозначает операцию побитового И. А $$$|$$$ обозначает операцию побитового ИЛИ.

Ваша цель — угадать $$$b.$$$

Взаимодействие происходит следующим образом:

  • Сначала вы отправляете интерактору значение $$$x$$$ такое, что $$$0 \le x \lt 2^{30}$$$.
  • Интерактор возвращает $$$v\,\mathrm{ty}\,x$$$. Формально, он возвращает $$$o(v,x)$$$, где $$$$$$o(v,x) = \begin{cases}v\,\&\,x & \mathrm{ty} = \& \\ v\,|\,x & \mathrm{ty} = |.\end{cases}$$$$$$
  • Затем вы отправляете два числа $$$m_0$$$ и $$$m_1$$$, где $$$0 \le m_0, m_1 \lt 2^{30}.$$$
  • Наконец, интерактор возвращает $$$m_b \oplus v,$$$ где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

После взаимодействия вы должны вывести $$$b$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных. Обратите внимание, что это единственный начальный ввод.

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

Сначала вам нужно вывести одно целое число $$$x \, (0 \le x \lt 2^{30})$$$ — начальное значение, которое нужно отправить интерактору.

В ответ вы получите одно целое число $$$o\,(0 \le o \lt 2^{30})$$$ — результат операции $$$o(v,x)$$$ над $$$v\,\mathrm{ty}\,x.$$$

Затем вы должны вывести одну строку, содержащую два целых числа $$$m_0, m_1\,(0 \le m_0, m_1 \lt 2^{30}).$$$

Наконец, получите одно целое число $$$r\,(0 \le r \lt 2^{30})$$$ — значение $$$m_b \oplus v.$$$

Обратите внимание, что интерактор частично адаптивный — в частности, выбор $$$v$$$ может зависеть от начального значения $$$x$$$, но все скрытые значения будут зафиксированы после этого.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

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

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
3

0

315

3

35

5

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

314 159

0

3

12 34

1

0

0 0

1
Примечание

Пример взаимодействия происходит следующим образом:

РешениеИнтеракторПояснение
$$$3$$$Есть $$$3$$$ набора входных данных.
$$$2$$$Решение выбирает $$$x = 2$$$.
$$$0$$$Интерактор возвращает $$$x\,\mathrm{ty}\,v = 2\,\&\,1 = 0.$$$
$$$314$$$ $$$159$$$Решение отправляет $$$m_0 = 314$$$ и $$$m_1 = 159.$$$
$$$315$$$Интерактор отвечает $$$m_b \oplus v = m_0 \oplus v = 315.$$$
$$$0$$$Решение определяет $$$b = 0.$$$
$$$3$$$Начинается следующий набор входных данных. Решение выбирает $$$x = 3$$$.
$$$3$$$Интерактор возвращает $$$x\,\mathrm{ty}\,v = 3\,|\,1 = 3.$$$
$$$12$$$ $$$34$$$Решение отправляет $$$m_0 = 12$$$ и $$$m_1 = 34.$$$
$$$35$$$Интерактор отвечает $$$m_b \oplus v = m_1 \oplus v = 35.$$$
$$$1$$$Решение определяет $$$b = 1.$$$
$$$0$$$Начинается последний набор входных данных. Решение выбирает $$$x = 0$$$.
$$$5$$$Интерактор возвращает $$$x\,\mathrm{ty}\,v = 0\,|\,5 = 5.$$$
$$$0$$$ $$$0$$$Решение отправляет $$$m_0 = 0$$$ и $$$m_1 = 0.$$$
$$$5$$$Интерактор отвечает $$$m_b \oplus v = m_1 \oplus v = 5.$$$
$$$1$$$Решение определяет $$$b = 1.$$$

Обратите внимание, что запросы, сделанные решением из примера, могут не давать достаточно информации для определения скрытого бита $$$b.$$$ Кроме того, пустые строки в примере взаимодействия приведены только для удобства чтения и не обязаны выводиться в решении.

Скрытые значения в наборах входных данных приведены ниже.

Набор #$$$v$$$$$$b$$$$$$\mathrm{ty}$$$
$$$1$$$$$$1$$$$$$0$$$$$$\&$$$
$$$2$$$$$$1$$$$$$1$$$$$$|$$$
$$$3$$$$$$5$$$$$$1$$$$$$|$$$