Это интерактивная задача.
Имеется сетка конвейерных лент размером \(n\) на \(n\), расположенных в позициях с \((1, 1)\) по \((n, n)\) координатной плоскости. Все остальные клетки плоскости пусты. Каждый конвейер может быть настроен на перемещение коробок вверх ('^'), вниз ('v'), влево ('<') или вправо ('>'). Если клетка перемещается на пустую клетку, она прекращает движение.
Однако, одна из \(n^2\) лент застряла, и всегда будет перемещать ящики в одном и том же направлении, независимо от того, как она настроена. Ваша цель - провести серию тестов, чтобы определить, какая лента застряла, и в каком направлении она посылает предметы.
Для достижения этой цели вы можете провести до \(25\) тестов. В каждом тесте вы задаете направление всем \(n^2\) лентам, ставите коробку на одну из них, а затем включаете все конвейеры.
Один из возможных результатов запроса с \(n=4\). В этом случае ящик начинается с \((2, 2)\). Если бы не было застрявшего конвейера, она бы закончилась в \((5, 4)\), но из-за застрявшего конвейера '>' в \((3, 3)\) она попадает в бесконечный цикл.Конвейеры перемещают коробку слишком быстро, чтобы вы могли ее увидеть, поэтому единственная информация, которую вы получаете от теста - это то, остановилась ли коробка в конце концов, и если да, то координаты ее конечного положения.
Протокол взаимодействия
Вы начинаете взаимодействие с чтения одного целого числа \(n\) (\(2 \le n\le 100\)) — количество строк и столбцов в сетке.
Затем вы можете сделать не более \(25\) запросов.
Каждый запрос должен начинаться со строки вида ?r c, где r и c - начальные строка и столбец ячейки, соответственно.
Следующие \(n\) строк запроса должны содержать по \(n\) символов. \(j\)-й символ \(i\)-й строки должен быть одним из '^', 'v', '<' или '>', указывая направление конвейера \((i, j)\) для данного запроса.
После каждого запроса вы получите два целых числа \(x\) и \(y\). Если \(x = y = -1\), то ящик вошел в бесконечный цикл. В противном случае его конечное положение было \((x, y)\).
Если вы сделаете слишком много запросов или сделаете неправильный запрос, вы получите вердикт Неправильный ответ.
После того как вы нашли застрявший конвейер и его направление, выведите единственную строку ! r c dir, где r и c - строка и столбец застрявшего конвейера соответственно, а dir - один из символов '^', 'v', '<' или '>', указывающий направление застрявшего конвейера. Обратите внимание, что вывод ответа не засчитывается в \(25\) запросов. После вывода этой строки ваша программа должна завершиться.
Интерактор является неадаптивным. Это означает, что местоположение и направление застрявшего конвейера фиксировано в начале взаимодействия и не меняется после выполнения запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат.
Первая строка должна содержать одно целое число \(n\) (\(1 \le n \le 100\)) — количество строк и столбцов в сетке.
Следующая строка должна содержать два целых числа \(r\) и \(c\) (\(1 \le r, c \le n\)), а также символ \(\mathrm{dir}\) (\(\mathrm{dir}\) - одно из '^', 'v', '<', '>') — положение застрявшего конвейера и его фиксированное направление. Эти значения должны быть разделены пробелами.
Примечание
В первом запросе первого примера ящик стартует на \((2, 2)\) и входит в бесконечный цикл, содержащий строки \(2\) и \(3\). Поскольку застрявший конвейер находится в ряду \(1\), он не влияет на результат запроса.
Во втором запросе первого примера конвейеры настроены аналогичным образом, но ящик стартует с \((1, 1)\). Если бы не было застрявшего конвейера, он попал бы в бесконечный цикл между \((1, 2)\) и \((1, 3)\). Однако застрявший конвейер перенаправляет его на \((0, 2)\).
После этих двух запросов программа определяет, что застрявший конвейер находится в точке \((1, 2)\) и направляет предметы вверх.
Запрос для второго примера соответствует картинке выше. После запроса существует множество вариантов застрявшего конвейера, но программа правильно определяет, что он находится в точке \((3, 3)\) и направляет предметы вправо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
-1 -1
0 2
|
? 2 2
>><
>>v
^<<
? 1 1
>><
>>v
^<<
! 1 2 ^
|
|
2
|
4
-1 -1
|
? 2 2
v>v<
^vv^
>v>v
! 3 3 >
|