CF2135B For the Champion

This is an interactive problem. The RiOI team is hosting a robot championship! This time, your robot is teleported into an infinite 2D plane with the Cartesian coordinate system on it. There are $$$n$$$ anchor points on the plane, and the coordinates of the $$$i$$$-th anchor point are $$$(x\_i, y\_i)$$$ ($$$-10^9\\le x\_i,y\_i\\le 10^9$$$). These are given to your robot by the jury as soon as it is teleported into the plane. However, your robot doesn't know its initial coordinates at first. To test the IQ of your robot, the RiOI team has come up with an interesting game. Your robot needs to find out the initial coordinates $$$(X, Y)$$$ ($$$-10^9\\le X, Y\\le 10^9$$$) by making the following moves. In one move, assuming that its current coordinates are $$$(a,b)$$$, your robot can choose a non-negative integer $$$k$$$ ($$$0\\le k\\le 10^9$$$) and do one of the following four types of operations: - Move up by $$$k$$$ units, i.e., your robot will move to $$$(a,b+k)$$$; - Move down by $$$k$$$ units, i.e., your robot will move to $$$(a,b-k)$$$; - Move left by $$$k$$$ units, i.e., your robot will move to $$$(a-k,b)$$$; - Move right by $$$k$$$ units, i.e., your robot will move to $$$(a+k,b)$$$. After each move, the jury will give the minimum Manhattan Distance between the current coordinates of your robot and any anchor point. More formally, assuming that the coordinates of your robot are $$$(c,d)$$$ after the move, the jury will output $$$$$$ \\min\_{1\\le i\\le n}\\left ( \\left|x\_i-c\\right|+\\left|y\_i-d\\right|\\right ). $$$$$$ To win the prize, you must prove that your robot has a high IQ. So you have to write a program for your robot to find its initial coordinates $$$(X, Y)$$$ in no more than $$$10$$$ moves.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \\le t \\le 100$$$). The description of the test cases follows. The first line of each test case contains a single integer $$$n$$$ ($$$1\\le n\\le 100$$$) — the number of anchor points. Then $$$n$$$ lines follow, the $$$i$$$-th line contains two integers $$$x\_i$$$ and $$$y\_i$$$ ($$$-10^9\\le x\_i,y\_i\\le 10^9$$$) — the coordinates of the $$$i$$$-th anchor point. It is guaranteed that the coordinates of the anchor points are pairwise distinct.

N/A

Here is the progress of the example: SolutionJuryExplanation2There are $$$2$$$ test cases in this test.1There is $$$1$$$ anchor point in this test case.0 0The coordinates of the only anchor point are $$$(0,0)$$$.The jury chooses $$$(100,99)$$$ as the robot's initial coordinates.? D 99100The robot moves down by $$$99$$$ units, and its current coordinates are $$$(100, 0)$$$. Then, the jury prints $$$|100-0|+|0-0|=100$$$ as the response to this move.? L 1011The robot moves left by $$$101$$$ units, and its current coordinates are $$$(-1, 0)$$$. Then, the jury prints $$$|(-1)-0|+|0-0|=1$$$ as the response to this move.! 100 99The robot has somehow determined its initial coordinates and reports the answer. Since the output is correct, the jury continues to the next test case.4There are $$$4$$$ anchor points in this test case.1 1The coordinates of the first anchor point are $$$(1,1)$$$.2 2The coordinates of the second anchor point are $$$(2,2)$$$.3 3The coordinates of the third anchor point are $$$(3,3)$$$.-1 -1The coordinates of the fourth anchor point are $$$(-1,-1)$$$.The jury chooses $$$(-1,0)$$$ as the robot's initial coordinates.? L 01The robot moves left by $$$0$$$ units, i.e., stays at the same position. Then, the jury prints $$$|(-1)-(-1)|+|0-(-1)|=1$$$ as the response to this move. It can be shown that this is the minimum Manhattan Distance between the robot and any anchor point.? U 12The robot moves up by $$$1$$$ unit, and its current coordinates are $$$(-1, 1)$$$. Then, the jury prints $$$|(-1)-(-1)|+|1-(-1)|=2$$$ as the response to this move.? R 20The robot moves right by $$$2$$$ units, and its current coordinates are $$$(1, 1)$$$. Then, the jury prints $$$|1-1|+|1-1|=0$$$ as the response to this move.! -1 0The robot has somehow determined its initial coordinates and reports the answer. Since the output is correct and there are no more test cases, the jury and the solution exit.