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

Имеется сетка конвейерных лент размером $$$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', '<', '>') — положение застрявшего конвейера и его фиксированное направление. Эти значения должны быть разделены пробелами.