D. Злой храм и двигающиеся камни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Важная информация: Вы не должны взламывать по этой задаче, так как претесты содержат все возможные тесты. Это значит, если Ваше решение пройдет претесты, Ваше решение пройдет финальное тестирование.

Вы — искатель приключений. Сейчас Вы путешествуете по злому храму. Одолев пару слабых чудищ, Вы прибыли в квадратную комнату, состоящую из плиток, выложенных в таблицу размера n × n. Комната полностью окружена стенами. В дальнем углу комнаты лежит дверь, закрытая злыми магическими силами. На двери написано следующее:

Дверь пробудит звук сталкивающихся камней!

Так как Вы довольно опытный искатель приключений, Вы мгновенно понимаете, в чем тут дело. В соседней комнате лежит бесконечное количество магических камней. Камни бывают четырех типов:

  • '^': этот камень двигается вверх;
  • '<': этот камень двигается влево;
  • '>': этот камень двигается вправо;
  • 'v': этот камень двигается вниз.

Чтобы открыть дверь, необходимо сначала поместить камни на некоторые плитки (одна плитка может быть занята не более чем одним камнем). Затем вы выбираете один из размещенных Вами камней и активируете его. Активированный камень будет двигаться в своем направлении, пока не встретит другой камень или попадет в стену комнаты (камень не будет двигаться, если что-то уже блокирует его в соответствующем направлении). Затем камень отключается. Если он ударяется о стену, или если уже произошло 107 активаций, то движение прекращается. В противном случае, ударенный камень активируется и процесс продолжается.

Если камень движется хотя бы одну ячейку, прежде чем попасть в стену, или другой камень, удар производит звук. Дверь откроется, как только число произведенных звуков достигнет по крайней мере x. Возможно, что камни будут двигаться и после получения x звуков.

Следующий рисунок иллюстрирует четыре возможных сценария передвижения камней.

  • Движется хотя бы одну ячейку и ударяется о камень. Слышится звук, ударенный камень активируется.
  • Движется хотя бы одну ячейку и ударяется о стену (то есть, бок комнаты). Слышится звук, движения прекращаются.
  • Не двигается, так как на пути стоит камень. Блокирующий камень активируется, но звука нет.
  • Не движется, так как впереди стена. Звука нет и движения прекращаются.

Предположим, что в соседней комнате лежит бесконечное количество камней каждого типа. Вы знаете, что надо делать: расставьте камни и откройте дверь!

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

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

  • n = 5, x = 5;
  • n = 3, x = 2;
  • n = 100, x = 105.

Все эти тестовые примеры будут содержаться в претестах.

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

Выведите n строк. Каждая строка состоит из n символов — j-ый символ i-ой строки указывает на содержимое плитки в j-ом столбце i-ой строки таблицы, его значение должно быть одним из следующих:

  • '^', '<', '>', или 'v': камень, как описано в условии задачи.
  • '.': пустая плитка.

Затем в следующей строке выведите два целых числа r и c (1 ≤ r, c ≤ n) — это значит, что камень, который Вы активизируете первым, находится в r-ой строке сверху и c-ом столбце слева. В этой ячейке должен быть камень.

Если есть несколько вариантов решения, можно выводить любой.

Примеры
Входные данные
5 5
Выходные данные
>...v
v.<..
..^..
>....
..^.<
1 1
Входные данные
3 2
Выходные данные
>vv
^<.
^.<
1 3
Примечание

Рассмотрим первый пример, ниже приведена его пошаговая симуляция вместе с количеством воспроизведенных звуков.

0 звуков
1 звук
2 звука
3 звука
4 звука
опять 4 звука

На картинке выше сначала активирован камень '^', потом камень '<'. Однако нет никакого звука, так как камень '^' не подвинулся ни на одну ячейку. Итак, 4 звука.

5 звуков

В этот момент 5 звуков уже есть, то есть решение верное. Однако, мы продолжим дальше, чтобы вы могли лучше понять условие.

6 звуков
7 звуков
опять 7 звуков
8 звуков

И движение оканчивается. В целом, произведено 8 звуков. Обратите внимание, что последнее движение производит звук.

Симуляция второго примера такова:

0 звуков
1 звук
2 звука

Теперь камни начинают активировать друг друга без звука, пока не достигнут лимита 107. После этого движение прекратится.

В целом, произведено ровно два звука и решение верно.