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

salyg1n подарил Алисе множество $$$S$$$ из $$$n$$$ различных целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq 10^9$$$). Алиса решила сыграть против Боба в игру с этим множеством. Правила игры таковы:

• Игроки ходят по очереди, первой ходит Алиса.

• Алиса за один ход добавляет в множество $$$S$$$ одно число $$$x$$$ ($$$0 \leq x \leq 10^9$$$). Множество $$$S$$$ не должно содержать число $$$x$$$ на момент хода.
• Боб за один ход удаляет из множества $$$S$$$ одно число $$$y$$$. Множество $$$S$$$ должно содержать число $$$y$$$ на момент хода. Также число $$$y$$$ должно быть строго меньше последнего добавленного Алисой числа.
• Игра заканчивается, когда Боб не может сделать ход или спустя $$$2 \cdot n + 1$$$ ходов (в таком случае последним ходом будет ход Алисы).
• Результатом игры назовем $$$\operatorname{MEX}\dagger(S)$$$ ($$$S$$$ на момент конца игры).
• Алиса стремится максимизировать результат, а Боб минимизировать.

Пусть $$$R$$$ — результат при оптимальной игре обоих игроков. В этой задаче вы играете за Алису против программы жюри, играющей за Боба. Ваша задача — реализовать стратегию Алисы, при которой результат игры всегда будет не меньше $$$R$$$.

$$$\dagger$$$ $$$\operatorname{MEX}$$$ набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$. Например, $$$\operatorname{MEX}(\{0, 1, 2, 4\})$$$ $$$=$$$ $$$3$$$.

Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания целого числа $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — размера множества $$$S$$$ до начала игры.

Затем считайте одну строку — $$$n$$$ различных целых чисел $$$s_i$$$ $$$(0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9)$$$ — множество $$$S$$$ подаренное Алисе.

Чтобы сделать ход выведите целое число $$$x$$$ ($$$0 \leq x \leq 10^9$$$) — число которое вы хотите добавить в множество $$$S$$$. $$$S$$$ не должно содержать $$$x$$$ на момент хода. Затем считайте одно целое число $$$y$$$ $$$(-2 \leq y \leq 10^9)$$$.

• Если $$$0 \leq y \leq 10^9$$$ — Боб удаляет число $$$y$$$ из множества $$$S$$$. Ваш ход!
• Если $$$y$$$ $$$=$$$ $$$-1$$$ — игра закончена. После этого следует приступать к обработке следующего тестового случая или завершить программу, если это был последний тестовый случай.
• Иначе $$$y$$$ $$$=$$$ $$$-2$$$. Это значит, что вы сделали некорректный запрос. Ваша программа должна немедленно завершится, чтобы получить вердикт Неправильный ответ. Иначе она может получить любой другой вердикт.

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

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

По этой задаче нельзя делать взломы.