D. Ленты конвейера
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Автоматизированная Пекарня Киберленда недавно купила прямоугольный стол, представляющий собой сетку размера 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.

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

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

В первой строке заданы три целых числа n, m и q (1 ≤ n ≤ 105, 1 ≤ m ≤ 10, 1 ≤ q ≤ 105), разделенных пробелом.

Далее следует n строк, в каждой из которых содержится по m символов, описывающих таблицу. Все символы принадлежат набору "<^>".

Далее следует q строк, в каждой из которых содержится по событию в формате: "C x y c" или "A x y". Гарантируется, что 1 ≤ x ≤ n, 1 ≤ y ≤ m. c — символ из множества "<^>".

Среди запросов не более 10000 имеет тип "C".

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

Для каждого события типа "A", выведите два разделённых пробелами целых числа tx, ty, обозначающих, что булка, запущенная в (x, y), в покинет стол в позиции (tx, ty).

Если булка застрянет, выведите tx = ty =  - 1.

Примеры
Входные данные
2 2 3
>>
^^
A 2 1
C 1 2 <
A 2 1
Выходные данные
1 3
-1 -1
Входные данные
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
Примечание

Для первого примера:

Если булка запущена в (2, 1), она покинет стол в (1, 3).

После того, как лента конвейера (1, 2) поменяется на "<", если запустить булку от (2, 1) ещё раз, она застрянет на "><", так что выводом на этот запрос является ( - 1,  - 1).