Geo Game
Contest: Codeforces Round 912 (Div. 2)
Difficulty rating: 2000
Tags: greedy, interactive, math

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
Second

4

6

3
First
1

4

Editorial:
If we went from point $$$(a,b)$$$ to $$$(c,d)$$$ then we will add to the sum $$$a^2 + c^2 - 2ac + b^2 + d^2 - 2bd$$$ which is equal to $$$a \oplus b \oplus c \oplus d$$$ mod $$$2$$$ ($$$\oplus$$$ is bitwise xor).
For each point, we find ($$$x$$$ mod $$$2$$$) $$$\oplus$$$ ($$$y$$$ mod $$$2$$$).
Let $$$p_0 =$$$ the number of ($$$x$$$ mod $$$2$$$) $$$\oplus$$$ ($$$y$$$ mod $$$2$$$) $$$== 0$$$, $$$p_1 =$$$ the number of ($$$x$$$ mod $$$2$$$) $$$\oplus$$$ ($$$y$$$ mod $$$2$$$) $$$== 1$$$ and $$$v =$$$ ($$$s_x$$$ mod $$$2$$$) $$$\oplus$$$ ($$$s_y$$$ mod $$$2$$$).
Let's say that we create a binary string starting with $$$v$$$ and has another $$$p_0$$$ zeros and $$$p_1$$$ ones.
If the number of $$$s_i \neq s_{i+1}$$$ is odd then the sum will be odd otherwise the sum will be even.
If you are the first player then you want to have an even number of $$$s_i \neq s_{i+1}$$$.
That holds iff the first element of $$$s$$$ is the same as the last element of $$$s$$$.
Thus, the second player will want to put all $$$p_v$$$ occurrences of $$$v$$$ before the end (so that the last element is not equal to the first).
He can do this iff $$$p_v < (n - 1) / 2$$$ (rounded down) (this means that $$$p_v < p_{v \oplus 1}$$$).
If $$$p_{v \oplus 1} \le p_v$$$ you play as the first player and you choose occurrences of $$$v \oplus 1$$$ until there aren't any
and else ($$$p_v < p_{v \oplus 1}$$$) you play as the second player and you choose occurrences of $$$v$$$ until there aren't any.