该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

这是一道交互题，你如果不太了解该题型，可以阅读 有关I/O交互题型的介绍 一文

Qsy 给了 Alice 一个包含 $n$ 个不同整数的集合 $S$：$s_1, s_2, \ldots, s_n$（$0 \leq s_i \leq 10^9$）。Alice 决定用这个集合和 Bob 玩一个游戏。游戏规则如下：

玩家轮流行动，Alice 先手。

在 Alice 的回合中，她向集合 $S$ 中添加一个数字 $x$（$0 \leq x \leq 10^9$）。添加时，集合 $S$ 中不能已包含数字 $x$。

在 Bob 的回合中，他从集合 $S$ 中移除一个数字 $y$。移除时，集合 $S$ 中必须包含数字 $y$。此外，数字 $y$ 必须严格小于 Alice 上一次添加的数字。

当 Bob 无法进行移动或总移动次数达到 $2 \cdot n + 1$ 次时（此时 Alice 的移动将是最后一次），游戏结束。

游戏的结果是 $\operatorname{MEX}\dagger$（游戏结束时集合 $S$ 的 $\operatorname{MEX}$）。

Alice 的目标是最大化结果，而 Bob 的目标是最小化结果。

设 $R$ 为双方都采取最优策略时的结果。在此问题中，你将扮演 Alice，与扮演 Bob 的判题程序对抗。 你的任务是为 Alice 实现一个策略，使得游戏的结果总是至少为 $R$。

$\dagger$ 整数集合 $c_1, c_2, \ldots, c_k$ 的 $\operatorname{MEX}$ 定义为集合中未出现的最小非负整数 $x$。例如，$\operatorname{MEX}({0, 1, 2, 4}) = 3$。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）——测试用例的数量。 交互

你的程序与判题程序的交互从读取一个整数 $n$（$1 \leq n \leq 10^5$）开始，表示游戏开始前集合 $S$ 的大小。

接着，读取一行——$n$ 个不同的整数 $s_i$（$0 \leq s_1 < s_2 < \ldots < s_n \leq 10^9$），表示给 Alice 的初始集合 $S$。

要执行一次移动，请输出一个整数 $x$（$0 \leq x \leq 10^9$）——你想添加到集合 $S$ 中的数字。此时集合 $S$ 中不能包含 $x$。然后，读取一个整数 $y$（$-2 \leq y \leq 10^9$）。

如果 $0 \leq y \leq 10^9$，表示 Bob 从集合 $S$ 中移除了数字 $y$。现在轮到你了！

如果 $y = -1$，表示游戏结束。之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。

否则，$y = -2$。这表示你的查询无效。你的程序应立即终止，否则可能会收到 Wrong Answer 的判决。

在输出查询后，请勿忘记输出行尾并刷新输出。否则，你将收到 Idleness limit exceeded。为此，请使用：

在 C++ 中使用 fflush(stdout) 或 cout.flush()；

在 Java 中使用 System.out.flush()；

在 Pascal 中使用 flush(output)；

在 Python 中使用 stdout.flush()；

其他语言请参考相关文档。

保证所有测试用例的 $n$ 的总和不超过 $10^5$。

样例

3
5
1 2 3 5 7

7

5

-1

3
0 1 2

0

-1

3
5 7 57

-1

8

57

0

3

0

0

限制与提示

在第一个测试用例中，集合 $S$ 的变化如下：

{$1, 2, 3, 5, 7$} $\to$ {$1, 2, 3, 5, 7, 8$} $\to$ {$1, 2, 3, 5, 8$} $\to$ {$1, 2, 3, 5, 8, 57$} $\to$ {$1, 2, 3, 8, 57$} $\to$ {$0, 1, 2, 3, 8, 57$}。游戏结束时，$\operatorname{MEX}(S) = 4$，$R = 4$。

在第二个测试用例中，集合 $S$ 的变化如下：

{$0, 1, 2$} $\to$ {$0, 1, 2, 3$} $\to$ {$1, 2, 3$} $\to$ {$0, 1, 2, 3$}。游戏结束时，$\operatorname{MEX}(S) = 4$，$R = 4$。

在第三个测试用例中，集合 $S$ 的变化如下：

{$5, 7, 57$} $\to$ {$0, 5, 7, 57$}。游戏结束时，$\operatorname{MEX}(S) = 1$，$R = 1$。