CF1903E.Geo Game

This is an interactive problem.

Theofanis and his sister are playing the following game.

They have $n$ points in a 2D plane and a starting point $(s_x,s_y)$. Each player (starting from the first player) chooses one of the $n$ points that wasn't chosen before and adds to the sum (which is initially $0$) the square of the Euclidean distance from the previous point (which is either the starting point or it was chosen by the other person) to the new point (that the current player selected).

The game ends after exactly $n$ moves (after all the points are chosen). The first player wins if the sum is even in the end. Otherwise, the second player wins.

Theofanis is a very competitive person and he hates losing. Thus, he wants to choose whether he should play first or second. Can you show him, which player to choose, and how he should play to beat his sister?

这是一个交互式问题。

西奥法尼斯和他的妹妹正在玩以下游戏：

他们在二维平面上有 $n$ 个点，以及一个起始点 $(s_x,s_y)$。每名玩家（从先手玩家开始）轮流选择一个尚未被选过的点（共 $n$ 个点中的一个），并将该点与上一个点（若为第一步，则上一个点即为起始点 $(s_x,s_y)$；否则为对方上一轮所选的点）之间的欧几里得距离的平方加到总和中（初始总和为 $0$）。

游戏恰好进行 $n$ 轮（即所有 $n$ 个点均被选完后）结束。若最终总和为偶数，则先手玩家获胜；否则，后手玩家获胜。

西奥法尼斯是一个极具竞争意识的人，他非常讨厌失败。因此，他希望决定自己应该选择先手还是后手。你能告诉他应选择哪一方，并给出必胜策略，以确保他战胜妹妹吗？

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The data for each test case is only available after the end of the interaction (the end of the game) for all previous test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{5}$) — the number of points.

The second line of each test case contains two integers $s_x$, $s_y$ ($0 \le s_x, s_y \le 10^{9}$) — the coordinates of the starting point.

Two or more points may have the same coordinates.

The $i$-th of the following $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^{9}$) — the coordinates of the $i$-th point.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^{5}$.

第一行包含一个整数 $t$（$1 \le t \le 2000$）—— 表示测试用例的数量。

每个测试用例的数据仅在所有先前测试用例的交互（即游戏）结束后才可用。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^{5}$）—— 表示点的数量。

每个测试用例的第二行包含两个整数 $s_x$、$s_y$（$0 \le s_x, s_y \le 10^{9}$）—— 表示起点的坐标。

两个或更多点可能具有相同的坐标。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^{9}$）—— 表示第 $i$ 个点的坐标。

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

The examples above do not necessarily showcase optimal strategies or the correct player to choose.

In the picture below, you can see the moves that each player made in the first example. The first player is red, and the second player is black.

上述示例未必展示了最优策略，也未必表明应选择哪位玩家获胜。

在下方图片中，您可以查看第一个示例中每位玩家所走的棋步。先手玩家为红色，后手玩家为黑色。