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

Это интерактивная задача. Взломы отключены.

Вы участвуете в битве аур в Пачуке, Мексика. Каждая битва состоит из $$$10$$$ раундов. Судьи загадали целое число $$$x$$$ ($$$1 \le x \le 10^4$$$), которое не меняется на протяжении всей битвы.

В раунде $$$i$$$ вы выбираете два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$-10^9 \le a_i, b_i \le 10^9$$$). Затем вы теряете $$$$$$ \min\bigl(|x-a_i|,\ |x-b_i|\bigr) $$$$$$ единиц ауры и до начала следующего раунда узнаёте это количество. Ваш выбор может зависеть от результатов всех предыдущих раундов. После окончания битвы общая потеря ауры вычисляется как сумма потерь ауры во всех $$$10$$$ раундах.

Пусть $$$m$$$ — наименьшее целое число, для которого существует стратегия, гарантирующая общую потерю не более $$$m$$$ единиц ауры независимо от скрытого значения $$$x$$$. Ваша задача — гарантировать общую потерю ауры, не превышающую лимит: $$$10^5$$$ в первом тесте (примере) и $$$m+67$$$ во всех остальных тестах.

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

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество битв.

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

$$$t$$$ битв проводятся одна за другой. В каждой битве повторите следующие действия $$$10$$$ раз:

  • выведите два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$-10^9 \le a_i, b_i \le 10^9$$$) — значения, которые вы выбираете в $$$i$$$-м раунде;
  • считайте одно целое число $$$p$$$ — количество ауры, потерянной в этом раунде, то есть $$$p = \min(\lvert x - a_i \rvert, \lvert x - b_i \rvert)$$$, где $$$x$$$ — скрытое значение в текущей битве.

Вы должны сыграть все $$$10$$$ раундов битвы.

Между битвами ничего не выводится и не считывается: сразу после $$$10$$$-го раунда одной битвы начинается следующая, а после $$$10$$$-го раунда последней битвы ваша программа должна завершиться, ничего больше не выводя.

Если вы выведете значение за пределами $$$[-10^9, 10^9]$$$, интерактор перестанет отвечать, а вы получите вердикт Неправильный ответ. В таком случае немедленно завершите программу, иначе вы можете получить произвольный вердикт. Вы также получите вердикт Неправильный ответ, если общая потеря ауры в какой-либо битве превысит лимит: $$$10^5$$$ в первом тесте (примере) и $$$m+67$$$ во всех остальных тестах.

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

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

13

4

2

2

4

5

9

6

9

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

3 53

36 49

47 38

1 38

44 32

35 35

31 67

33 46

49 50

20 27
Примечание

В примере проводится одна битва, а скрытое значение $$$x$$$ равно $$$40$$$.

  • В первом раунде $$$a_1 = 3$$$ и $$$b_1 = 53$$$, поэтому вы теряете $$$13 = \min(\lvert 3 - 40 \rvert, \lvert 53 - 40 \rvert)$$$ единиц ауры.
  • Во втором раунде $$$a_2 = 36$$$ и $$$b_2 = 49$$$, поэтому вы теряете $$$4 = \min(\lvert 36 - 40 \rvert, \lvert 49 - 40 \rvert)$$$ единицы ауры.
  • В третьем раунде вы теряете $$$2$$$ единицы ауры.
  • В последующих раундах вы теряете соответственно $$$2, 4, 5, 9, 6, 9, 13$$$ единиц ауры.

Суммарно вы теряете $$$67$$$ единиц ауры. Заметим, что это лишь пример работы взаимодействия. Чтобы получить вердикт «OK», необходимо решить задачу, не превышая указанный выше лимит потери ауры.