B. Tread Lightly
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a run-twice (communication) interactive problem.

There are two players: Player A and Player B. The jury (otherwise known as the interactor of this problem) will first interact with player A. After player A ends their interaction, the jury will interact with player B. Note that player A and player B may not directly pass information to each other; both players are only able to send information to or receive information from the jury.

There is a hidden $$$n \times n$$$ grid. It contains two special points: a pile of money at $$$M = (x_M, y_M)$$$ and a bomb at $$$B = (x_B, y_B)$$$. This setup is determined by the jury before the interaction, and is consistent across both players.

Player A receives the value of $$$n$$$ and the points $$$M$$$ and $$$B$$$ from the jury. Then, Player A must send an integer $$$k$$$ ($$$1 \le k \le x$$$) back to the jury, where $$$x$$$ is the limit on $$$k$$$.

Player B receives the value of $$$n$$$ and the value of $$$k$$$ (the same integer that Player A sent) from the jury. Their task is to determine the coordinates of point $$$M$$$. To do so, Player B can make at most $$$100$$$ queries of the form $$$(x, y, d)$$$ where $$$(x, y)$$$ is a point on the grid and $$$d$$$ is a direction (up/down/left/right).

  • If $$$(x, y)$$$ is in the same row or column as $$$B$$$ (i.e., $$$x = x_B$$$ or $$$y = y_B$$$ or both), then the jury will return "Boom" as the bomb explodes and burns down the money. Note that this can happen even if $$$(x, y) = M$$$, as long as $$$(x, y)$$$ is in the same row or column as $$$B$$$. Player B should give up (terminate gracefully) after a "Boom" as the money is gone.
  • Otherwise, the jury will return "Yes" or "No" depending on whether the point $$$M$$$ is in $$$d$$$ direction of $$$(x, y)$$$.
    • For $$$d = U$$$ (up), $$$M$$$ is in $$$U$$$ direction of $$$(x, y)$$$ if $$$x_M \lt x$$$.
    • For $$$d = D$$$ (down), $$$M$$$ is in $$$D$$$ direction of $$$(x, y)$$$ if $$$x_M \gt x$$$.
    • For $$$d = L$$$ (left), $$$M$$$ is in $$$L$$$ direction of $$$(x, y)$$$ if $$$y_M \lt y$$$.
    • For $$$d = R$$$ (right), $$$M$$$ is in $$$R$$$ direction of $$$(x, y)$$$ if $$$y_M \gt y$$$.

Player A wants to ensure that player B can determine the coordinates of $$$M$$$. Let $$$x_{min}$$$ be the minimum value of the limit $$$x$$$ for which Player B can always do so safely, for any value $$$2 \le n \le 10^9$$$ and any valid coordinates for $$$M$$$ and $$$B$$$. Note that this value $$$x_{min}$$$ is a provable constant and is known to the jury — although you do not have to prove it (your solution only needs to respect the $$$x_{min}$$$ limit).

Your task is to act as both players and determine an optimal interaction strategy for both players so that player B determines the coordinates correctly, such that the integer $$$k$$$ follows the constraints $$$1 \le k \le x_{min}$$$.

FIRST RUN

Your code will run exactly twice on each test. On the first run, you will be Player A.

Input

The first line of the input contains the string "first". The purpose of this is so your program recognises that this is its first run, and it should act as Player A.

The second line of the input contains exactly one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains exactly one integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the dimension of the grid.

The second line of each test case contains two space-separated integers $$$x_M$$$ and $$$y_M$$$ ($$$1 \le x_M, y_M \le n$$$) — the coordinates of $$$M$$$.

The third line of each test case contains two space-separated integers $$$x_B$$$ and $$$y_B$$$ ($$$1 \le x_B, y_B \le n$$$) — the coordinates of $$$B$$$.

Output

For each test case, print an integer $$$k$$$ ($$$1 \le k \le x_{min}$$$) on a new line. This is the integer that will be sent to you in the second run.

After this, proceed to the next test case, or terminate your program if it was the last test case.

SECOND RUN

On the second run, you are Player B.

Input

The first line of the input contains the string "second". The purpose of this is so your program recognises that this is its second run, and it should act as Player B.

The second line of the input contains exactly one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Note that this number is equal to $$$t$$$ from the first run input.

The first line of each test case contains exactly one integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the dimension of the grid. Note that this number is equal to $$$n$$$ from the first run input.

The second line of each test case contains exactly one integer $$$k$$$ ($$$1 \le k \le x_{min}$$$) — the integer that was sent by Player A from the first run.

Note that the test cases in the second run may be shuffled. Please see the example test case for further illustration.

Interaction

For each test case, recall you will first receive $$$n$$$ and $$$k$$$ in the input from the jury according to the input format above.

After receiving those inputs, you will be able to make at most $$$100$$$ queries of the following format: "? x y d" ($$$1 \le x, y \le n$$$ and $$$d \in \{U, D, L, R\}$$$).

After each query, the jury will respond with "Boom", "Yes", or "No" as described in the statement above. If you receive a "Boom" response in the same test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Once you are ready to report the coordinates of $$$M$$$, you may do so in the format: "! x y" ($$$1 \le x, y \le n$$$), where $$$(x, y)$$$ is the coordinates you wish to report.

Then, you will either proceed to the next test case, or your program must terminate if you have processed every test case. Reporting the answer does not count towards the number of queries made.

The interactor is not adaptive. That is, the points $$$M$$$ and $$$B$$$ will not change during the interaction, and will always be the same positions as shown to you in the first run.

After printing each query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

Examples
Input
first
3
# Test case 1
2
1 1
2 2

# Test case 2
4
4 4
4 2

# Test case 3
3
2 1
3 2
Output
# Test case 1
1000000000

# Test case 2
1

# Test case 3
6
Input
second
3
# Test case 1
3
6
No
Yes
Yes

# Test case 2
2
1000000000
No

# Test case 3
4
1
Yes
No
Output
# Test case 1
? 2 1 R
? 1 3 L
? 1 1 D
! 2 1

# Test case 2
? 1 1 R
! 1 1

# Test case 3
? 3 3 D
? 3 3 L
! 4 4
Note
  1. You do not have to handle comments (lines starting with #) in the input; they are only for presentation purposes and will not be present in the test cases.
  2. The queries given in the sample input and output are for demonstrating the interaction, and may not logically lead to a correct output.
  3. The values of $$$k$$$ used in the sample output may not respect the limit $$$x_{min}$$$, and are only for demonstrating the interaction.

For the first run:

  • Test case 1: $$$n = 2$$$, $$$M = (1, 1)$$$, $$$B = (2, 2)$$$. According to some strategy between the players, Player A sends the integer $$$k = 1000000000$$$.
  • Test case 2: $$$n = 4$$$, $$$M = (4, 4)$$$, $$$B = (4, 2)$$$. According to some strategy between the players, Player A sends the integer $$$k = 1$$$.
  • Test case 3: $$$n = 3$$$, $$$M = (2, 1)$$$, $$$B = (3, 2)$$$. According to some strategy between the players, Player A sends the integer $$$k = 6$$$.

For the second run: Note that the test cases are re-ordered between runs. However, note that the integer $$$k$$$ for each test case is the same as what is given in the first run.

  • Test case 1 (previously test case 3 in the first run): $$$n = 4$$$, $$$M = (2, 1)$$$, $$$B = (3, 2)$$$, $$$k = 6$$$.
    • Player B queries $$$(2, 1, R)$$$. Since $$$(2, 1)$$$ is not right of $$$(2, 1)$$$ (as $$$1 \gt 1$$$ isn't true), the jury replies "No".
    • Player B queries $$$(1, 3, L)$$$. Since $$$(2, 1)$$$ is left of $$$(1, 3)$$$ (as $$$1 \lt 3$$$), the jury replies "Yes".
    • Player B queries $$$(1, 1, D)$$$. Since $$$(2, 1)$$$ is down of $$$(1, 1)$$$ (as $$$2 \gt 1$$$), the jury replies "Yes".
    • Player B correctly determines and reports the coordinates $$$(2, 1)$$$ for $$$M$$$.
  • Test case 2 (previously test case 1 in the first run): $$$n = 2$$$, $$$M = (1, 1)$$$, $$$B = (2, 2)$$$, $$$k = 1000000000$$$.
    • Player B queries $$$(1, 1, R)$$$. Since $$$(1, 1)$$$ is not right of $$$(1, 1)$$$ (as $$$1 \gt 1$$$ isn't true), the jury replies "No".
    • Player B correctly determines and reports the coordinates $$$(1, 1)$$$ for $$$M$$$.
  • Test case 3 (previously test case 2 in the first run): $$$n = 4$$$, $$$M = (4, 4)$$$, $$$B = (4, 2)$$$, $$$k = 1$$$.
    • Player B queries $$$(3, 3, D)$$$. Since $$$(4, 4)$$$ is down of $$$(3, 3)$$$ (as $$$4 \gt 3$$$), the jury replies "Yes".
    • Player B queries $$$(3, 3, L)$$$. Since $$$(4, 4)$$$ is not left of $$$(3, 3)$$$ (as $$$4 \lt 3$$$ isn't true), the jury replies "No".
    • Player B correctly determines and reports the coordinates $$$(4, 4)$$$ for $$$M$$$.