B. Для чемпиона
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Команда RiOI проводит чемпионат для роботов!

На этот раз ваш робот телепортируется на бесконечную двухмерную плоскость с декартовой системой координат. На плоскости находятся $$$n$$$ опорных точек, и координаты $$$i$$$-й опорной точки равны $$$(x_i, y_i)$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$). Жюри предоставляет эти данные вашему роботу сразу после телепортации на плоскость. Однако ваш робот изначально не знает своих координат.

Чтобы проверить IQ вашего робота, команда RiOI придумала интересную игру. Вашему роботу необходимо выяснить начальные координаты $$$(X, Y)$$$ ($$$-10^9\le X, Y\le 10^9$$$), совершая следующие движения.

Предположим, что $$$(a,b)$$$ — текущие координаты робота. За один ход ваш робот может выбрать целое неотрицательное число $$$k$$$ ($$$0\le k\le 10^9$$$) и выполнить одну из следующих четырех операций:

  • Подняться на $$$k$$$ единиц, т.е. ваш робот переместится в $$$(a,b+k)$$$;
  • Опуститься на $$$k$$$ единиц, т.е. ваш робот переместится в $$$(a,b-k)$$$;
  • Переместиться влево на $$$k$$$ единиц, т.е. ваш робот переместится в $$$(a-k,b)$$$;
  • Переместиться вправо на $$$k$$$ единиц, т.е. ваш робот переместится в $$$(a+k,b)$$$.

После каждого хода жюри сообщит минимальное манхэттенское расстояние между текущими координатами вашего робота и любой опорной точкой. Более формально, предположим, что координаты вашего робота равны $$$(c,d)$$$ после хода, тогда жюри выведет

$$$$$$ \min_{1\le i\le n}\left ( \left|x_i-c\right|+\left|y_i-d\right|\right ). $$$$$$

Чтобы выиграть приз, вы должны доказать, что ваш робот обладает высоким IQ. Поэтому вам нужно написать программу для вашего робота, чтобы найти его начальные координаты $$$(X, Y)$$$ не более чем за $$$10$$$ ходов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 100$$$) — количество опорных точек.

Затем следуют $$$n$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — координаты $$$i$$$-й опорной точки.

Гарантируется, что координаты опорных точек попарно различны.

Протокол взаимодействия

Для каждого набора входных данных сначала прочитайте целое число $$$n$$$ и координаты опорных точек. Затем вы можете сделать до $$$10$$$ ходов.

Чтобы сделать ход, вы должны вывести строку в одном из следующих форматов:

  • $$$\texttt{? U }k$$$ — подняться на $$$k$$$ единиц;
  • $$$\texttt{? D }k$$$ — опуститься на $$$k$$$ единиц;
  • $$$\texttt{? L }k$$$ — переместиться влево на $$$k$$$ единиц;
  • $$$\texttt{? R }k$$$ — переместиться вправо на $$$k$$$ единиц.

Вы должны гарантировать, что $$$0\le k\le 10^{9}$$$.

В конце каждого хода жюри выведет целое число $$$s$$$ — минимальное манхэттенское расстояние между текущими координатами вашего робота и любой опорной точкой.

Чтобы сообщить, что вы нашли начальные координаты вашего робота, выведите новую строку в следующем формате:

  • $$$\texttt{! }X\texttt{ }Y$$$ — начальные координаты вашего робота равны $$$(X, Y)$$$.

Вывод ответа не считается одним из $$$10$$$ ходов.

После этого продолжайте обрабатывать следующий набор входных данных или завершите программу, если это был последний набор входных данных.

Предположим, что начальные координаты вашего робота равны $$$(X, Y)$$$. Гарантируется, что $$$-10^{9}\le X, Y\le 10^{9}$$$.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взаимодействие в этой задаче не адаптивно. Другими словами, начальные координаты робота не изменяются в процессе взаимодействия.

Взломы

Чтобы выполнить взлом, используйте следующий формат:

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\le n\le 100$$$) — количество опорных точек.

Затем следуют $$$n$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9\le x_i,y_i\le 10^9$$$) — координаты $$$i$$$-й опорной точки.

В следующей строке выведите два целых числа $$$X$$$ и $$$Y$$$ ($$$-10^9\le X, Y\le 10^9$$$) — начальные координаты робота.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
1
0 0

100

1

4
1 1
2 2
3 3
-1 -1

1

2

0
Выходные данные



? D 99

? L 101

! 100 99





? L 0

? U 1

? R 2

! -1 0
Примечание

Разберём пример:

РешениеЖюриОбъяснение
2В этом тесте $$$2$$$ набора входных данных.
1В этом наборе входных данных $$$1$$$ опорная точка.
0 0Координаты единственной опорной точки равны $$$(0,0)$$$.
Жюри выбирает $$$(100,99)$$$ в качестве начальных координат робота.
? D 99100Робот опускается на $$$99$$$ единиц, и его текущие координаты равны $$$(100, 0)$$$. Затем жюри выводит $$$|100-0|+|0-0|=100$$$ в ответ на этот ход.
? L 1011Робот перемещается влево на $$$101$$$ единицу, и его текущие координаты равны $$$(-1, 0)$$$. Затем жюри выводит $$$|(-1)-0|+|0-0|=1$$$ в ответ на этот ход.
! 100 99Робот каким-то образом определил свои начальные координаты и сообщает ответ. Поскольку ответ верный, жюри переходит к следующему набору входных данных.
4В этом наборе входных данных $$$4$$$ опорные точки.
1 1Координаты первой опорной точки равны $$$(1,1)$$$.
2 2Координаты второй опорной точки равны $$$(2,2)$$$.
3 3Координаты третьей опорной точки равны $$$(3,3)$$$.
-1 -1Координаты четвертой опорной точки равны $$$(-1,-1)$$$.
Жюри выбирает $$$(-1,0)$$$ в качестве начальных координат робота.
? L 01Робот перемещается влево на $$$0$$$ единиц, т.е. остается на том же месте. Затем жюри выводит $$$|(-1)-(-1)|+|0-(-1)|=1$$$ в ответ на этот ход. Можно показать, что это минимальное манхэттенское расстояние между роботом и любой опорной точкой.
? U 12Робот поднимается на $$$1$$$ единицу, и его текущие координаты равны $$$(-1, 1)$$$. Затем жюри выводит $$$|(-1)-(-1)|+|1-(-1)|=2$$$ в ответ на этот ход.
? R 20Робот перемещается вправо на $$$2$$$ единицы, и его текущие координаты равны $$$(1, 1)$$$. Затем жюри выводит $$$|1-1|+|1-1|=0$$$ в ответ на этот ход.
! -1 0Робот каким-то образом определил свои начальные координаты и сообщает ответ. Поскольку ответ верный и больше нет наборов входных данных, жюри и решение завершают работу.