Teleporters and Gems II
Last time Duck was playing "Teleporters and Gems" online game, but this time he is going to collect a big gem in person! To solve this problem, it is not necessary to solve the previous one.
Duck has 5 teleporters, he wants to collect a big gem with the help of these teleporters. These teleporters not only help him teleport to any coordinates, but also receive the signal from that gem, which is measured by the manhattan distance from the target coordinates to the big gem. In other words, whenever Duck uses a teleporter, he will be sent to the place (x, y) he wants to visit and knows the distance from there to the gem |x - xgem| + |y - ygem|.
Unfortunately, Duck doesn't know the exact location of the big gem. He wants you to help him collect that gem by using at most 5 teleporters, meaning that for the last time to use a teleporter, the return distance must be 0. Once you receive 0, you must process next test case immediately. You can start at any random coordinates.
Interactive protocol
This is an interactive problem, you are going to communicate with the judge via standard input and output. To make sure your program output actually goes out, remember to flush the output buffer after printing each line.
Initially, your program should read a single line containing an integer T indicating the number of test cases. Then you need to process T test cases.
For each test case, your program needs to use standand output to send a single line with two integers "X Y" (with a whitespace between them, without double quotes), indicating the target coordinates you want to teleport to. In response, the judge will print a single line with one integer D to your input stream, which your program must read through standard input, indicating the manhattan distance between (X, Y) and the big gem. If D is 0, the gem is found so you must process next test case immediately. Otherwise, you can repeat the above procedure to start a new exchange. Note that the maximum number of exchanges is 5, which means you should not output something more than 5 times via standand output for each test case. Otherwise, you will receive wrong answer.
Constraints
1 ≤ T ≤ 100
-109 ≤ X, Y ≤ 109
Sample interaction
| Judge: | 2 | // Number of test cases |
| You: | 7 10 | // Start test case 1, you teleport to (7, 10) |
| Judge: | 3 | // Manhattan distance between (7, 10) and gem is 3 |
| You: | 5 11 | // You teleport to (5, 11) |
| Judge: | 2 | // Manhattan distance between (5, 11) and gem is 2 |
| You: | 5 9 | // You teleport to (5, 9) |
| Judge: | 0 | // Manhattan distance between (5, 9) and gem is 0. You found it by 3 teleporters. |
| You: | -3 1 | // Start test case 2, you teleport to (-3, 1) |
| Judge: | 7301 | // Manhattan distance between (-3, 1) and gem is 7301 |
| You: | -2451 -4852 | // You teleport to (-2451, -4852) |
| Judge: | 0 | // Manhattan distance between (-2451, -4852) and gem is 0. You found it by 2 teleporters. |