Автоматизированная Пекарня Киберленда недавно купила прямоугольный стол, представляющий собой сетку размера n × m. Для обедающих вокруг стола были расставлены стулья. Размер каждого стула равен единичному квадрату, то есть, всего было расставлено 2(n + m) стульев.
На каждом единичном квадрате расположена лента конвейера. Есть три типа конвейерных лент: "^", "<" и ">". Лента "^" перемещает попавшие на неё предметы вверх. "<" перемещает влево, а ">" перемещает вправо.
Пронумеруем строки от 1 до n сверху вниз, а столбцы — от 1 до m слева направо. Будем говорить, что стулья, находящиеся за верхней частью сетки, составляют строку 0, а находящиеся за нижней частью сетки — строку n + 1. Также назовем стулья слева от сетки и справа от сетки столбцами 0 и m + 1. В силу конструктивных особенностей конвейерных лент доставка еды к строке n + 1 невозможна.
Нам дана исходная сетка, на которой по порядку произойдёт q событий. Есть два типа событий:
- "A x y" означает, что булка появится в строке x и столбце y (обозначим такую позицию (x, y)). Булка будет следовать по лентам конвейера, пока не попадет к стулу обедающего. Возможно, булка застрянет где-то посреди стола. Ваша задача — симулировать процесс и вывести конечную позицию булки, либо установить, что булка попадет в бесконечный цикл.
- "C x y c" означает, что тип конвейерной ленты (x, y) изменен на c.
Запросы выполняются отдельно друг от друга, то есть, даже если булка попадет в бесконечный цикл, это не повлияет на последующие запросы.
Выходные данные
Для каждого события типа "A", выведите два разделённых пробелами целых числа tx, ty, обозначающих, что булка, запущенная в (x, y), в покинет стол в позиции (tx, ty).
Если булка застрянет, выведите tx = ty = - 1.
Примечание
Для первого примера:
Если булка запущена в (2, 1), она покинет стол в (1, 3).
После того, как лента конвейера (1, 2) поменяется на "<", если запустить булку от (2, 1) ещё раз, она застрянет на "><", так что выводом на этот запрос является ( - 1, - 1).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 3
>>
^^
A 2 1
C 1 2 <
A 2 1
|
1 3
-1 -1
|
|
2
|
4 5 7
><<^<
^<^^>
>>>^>
>^>>^
A 3 1
A 2 2
C 1 4 <
A 3 1
C 1 2 ^
A 3 1
A 2 2
|
0 4
-1 -1
-1 -1
0 2
0 2
|