310877: CF1903E. Geo Game

E. Geo Gametime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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}$.

Interaction

For each test case, you should first output the player that you want to play as (First or Second).

Then, you should play the game. When it's your turn, you should output the index $j$ ($1 \le j \le n$) of the point that you want to choose, and when it's the other player's turn, you should read the index that they choose.

When all the turns are done, continue with reading the input for the next test case, or finish the program, if there are none.

If you receive the integer $-1$ instead of an index or a valid value of $n$, it means your program has made an invalid move or has lost the game in the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a choice for a player, or a turn, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

To hack, use the following format.

The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of 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.

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.

The sum of $n$ over all test cases should not exceed $10^{5}$.

ExampleInput

2
6
4 6
7 6
8 5
2 1
6 2
6 4
3 3

2

5

1
4
1 1
3 2
2 1
3 3
1 2


2

3

Output

Second

4

6

3
First
1

4

Note

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.

题目大意：
这是一个交互式问题。Theofanis和他的妹妹在玩一个游戏。他们在二维平面上有n个点和一个起始点(s_x,s_y)。每位玩家（从第一位玩家开始）选择一个之前未被选择的点，并将从上一个点（起始点或另一位玩家选择的点）到新选择的点的欧几里得距离的平方加到总和（初始为0）上。游戏在恰好n次移动后结束（所有点都被选择后）。如果最终总和是偶数，则第一位玩家获胜；否则，第二位玩家获胜。Theofanis想要选择自己是第一位还是第二位玩家，并想知道如何玩才能打败他的妹妹。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤2000）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——点的数量。
- 第二行包含两个整数s_x, s_y（0≤s_x, s_y≤10^9）——起始点的坐标。
- 接下来的n行，每行包含两个整数x_i, y_i（0≤x_i, y_i≤10^9）——第i个点的坐标。

输出：
- 对于每个测试用例，首先输出你想扮演的玩家（First或Second）。
- 然后进行游戏。当轮到你时，输出你想选择的点的索引j（1≤j≤n），当轮到另一位玩家时，读取他们选择的索引。
- 当所有回合结束后，继续读取下一个测试用例的输入，如果没有测试用例了，则结束程序。

注意：在输出玩家的选择或回合后，不要忘记输出换行符并刷新输出，否则会得到“Idleness limit exceeded”。具体的刷新输出的方法取决于使用的编程语言。题目大意： 这是一个交互式问题。Theofanis和他的妹妹在玩一个游戏。他们在二维平面上有n个点和一个起始点(s_x,s_y)。每位玩家（从第一位玩家开始）选择一个之前未被选择的点，并将从上一个点（起始点或另一位玩家选择的点）到新选择的点的欧几里得距离的平方加到总和（初始为0）上。游戏在恰好n次移动后结束（所有点都被选择后）。如果最终总和是偶数，则第一位玩家获胜；否则，第二位玩家获胜。Theofanis想要选择自己是第一位还是第二位玩家，并想知道如何玩才能打败他的妹妹。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤2000）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——点的数量。 - 第二行包含两个整数s_x, s_y（0≤s_x, s_y≤10^9）——起始点的坐标。 - 接下来的n行，每行包含两个整数x_i, y_i（0≤x_i, y_i≤10^9）——第i个点的坐标。 输出： - 对于每个测试用例，首先输出你想扮演的玩家（First或Second）。 - 然后进行游戏。当轮到你时，输出你想选择的点的索引j（1≤j≤n），当轮到另一位玩家时，读取他们选择的索引。 - 当所有回合结束后，继续读取下一个测试用例的输入，如果没有测试用例了，则结束程序。 注意：在输出玩家的选择或回合后，不要忘记输出换行符并刷新输出，否则会得到“Idleness limit exceeded”。具体的刷新输出的方法取决于使用的编程语言。