CF1934D2.XOR Break — Game Version

This is an interactive problem.

This is the game version of the problem. Note that the solution of this problem may or may not share ideas with the solution of the solo version. You can solve and get points for both versions independently.

Alice and Bob are playing a game. The game starts with a positive integer $n$ , with players taking turns. On each turn of the game, the following sequence of events takes place:

• The player having the integer $p$ breaks it into two integers $p_{1}$ and $p_{2}$ , where $0 \lt p_{1} \lt p$ , $0 \lt p_{2} \lt p$ and $p_{1} \oplus p_{2} = p$ .
• If no such $p_{1}$ , $p_{2}$ exist, the player loses.
• Otherwise, the opponent does either select the integer $p_{1}$ or $p_{2}$ .
• The game continues with the selected integer. The opponent will try to break it.

As Alice, your goal is to win. You can execute a maximum of $63$ break operations. You have the choice to play first or second. The system will act for Bob.

Here $\oplus$ denotes the bitwise XOR operation.

Each test contains multiple test cases. The first line of input contains a single integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases.

The only line of each test case contains a single integer $n$ ( $1 \leq n \leq 10^{18}$ ) — the number the game starts with.

For each test case, the interaction begins by reading the integer $n$ .

After reading $n$ , print a single line containing either "first" or "second", denoting what you want to play as (as first or second correspondingly).

On Alice's turn, you are required to print two positive integers, $p_{1}$ and $p_{2}$ such that $0 \lt p_{1} \lt p$ , $0 \lt p_{2} \lt p$ and $p_{1} \oplus p_{2} = p$ . Here, $p$ equals one of the two integers printed by Bob in the previous turn. If no turn has occurred previously, $p$ is equal to $n$ . If Alice cannot perform a break operation, print "0 0" to receive a Wrong answer verdict.

On Bob's turn, you should read two integers, $p_{1}$ and $p_{2}$ such that $0 \lt p_{1} \lt p$ , $0 \lt p_{2} \lt p$ and $p_{1} \oplus p_{2} = p$ . Here, $p$ equals one of the two integers printed by Alice in the previous turn. If no turn has occurred previously, $p$ is equal to $n$ . If Bob cannot perform a break operation $p_{1} = 0$ and $p_2 = 0$ in which case you should proceed to the next test case.

If any break operation performed by Alice is invalid, the interactor prints "-1 -1" and your code should promptly exit to receive a wrong answer verdict.

If Alice performs $63$ turns and Bob can still execute a break operation on the current integers, the interactor prints "-1 -1", and your code should promptly exit to receive a wrong answer verdict.

After printing a query, 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.

In this problem, hacks are disabled.

Explanation for the interaction.

Interactor / BobAliceExplanation4 $t$ 1 $n$ for the first test casesecondAlice chooses to go second0 0Bob says he cannot break $p = 1$ 3 $n$ for the second test casefirstAlice chooses to go first1 2Alice breaks $p = 3$ into $p_1 = 1$ and $p_2 = 2$ 0 0Bob says he cannot break $p = 1$ or $p = 2$ 13 $n$ for the third test casefirstAlice chooses to go first10 7Alice breaks $p = 13$ into $p_1 = 10$ and $p_2 = 7$ 3 4Bob breaks $p = 7$ into $p_1 = 3$ and $p_2 = 4$ 1 2Alice breaks $p = 3$ into $p_1 = 1$ and $p_2 = 2$ 0 0Bob says he cannot break $p = 1$ or $p = 2$ 777777770001 $n$ for the fourth test casefirstAlice chooses to go first777777770000 1Alice breaks $p = 777\,777\,770\,001$ into $p_1 = 777\,777\,770\,000$ and $p_2 = 1$ 0 0Bob says he cannot perform break operation.This table is for explanation only and does not reflect the actual behavior of the interactor.

Note that in the last test case Bob could choose $p_1$ and perform a break operation but he gave up.