CF487D.Conveyor Belts

Automatic Bakery of Cyberland (ABC) recently bought an n × m rectangle table. To serve the diners, ABC placed seats around the table. The size of each seat is equal to a unit square, so there are 2(n + m) seats in total.

ABC placed conveyor belts on each unit square on the table. There are three types of conveyor belts: "^", "<" and ">". A "^" belt can bring things upwards. "<" can bring leftwards and ">" can bring rightwards.

Let's number the rows with 1 to n from top to bottom, the columns with 1 to m from left to right. We consider the seats above and below the top of the table are rows 0 and n + 1 respectively. Also we define seats to the left of the table and to the right of the table to be column 0 and m + 1. Due to the conveyor belts direction restriction there are currently no way for a diner sitting in the row n + 1 to be served.

Given the initial table, there will be q events in order. There are two types of events:

• "A x y" means, a piece of bread will appear at row x and column y (we will denote such position as (x, y)). The bread will follow the conveyor belt, until arriving at a seat of a diner. It is possible that the bread gets stuck in an infinite loop. Your task is to simulate the process, and output the final position of the bread, or determine that there will be an infinite loop.
• "C x y c" means that the type of the conveyor belt at (x, y) is changed to c.

Queries are performed separately meaning that even if the bread got stuck in an infinite loop, it won't affect further queries.

网络国自动面包店（ABC）最近购买了一张 $n \times m$ 的矩形餐桌。为了服务顾客，ABC 在餐桌四周放置了座位。每个座位的大小等于一个单位正方形，因此总共有 $2(n + m)$ 个座位。

ABC 在餐桌上的每个单位正方形上都铺设了传送带。传送带有三种类型：“^”、“<” 和 “>”。其中，“^” 表示将物品向上输送，“<” 表示向左输送，“>” 表示向右输送。

我们从上到下将行编号为 $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$。

所有查询相互独立：即使某块面包陷入无限循环，也不会影响后续查询。

The first line of input contains three integers n, m and q (1 ≤ n ≤ 105, 1 ≤ m ≤ 10, 1 ≤ q ≤ 105), separated by a space.

Next n lines, each line contains m characters, describing the table. The characters can only be one of "<^>".

Next q lines, each line describes an event. The format is "C x y c" or "A x y" (Consecutive elements are separated by a space). It's guaranteed that 1 ≤ x ≤ n, 1 ≤ y ≤ m. c is a character from the set "<^>".

There are at most 10000 queries of "C" type.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 ≤ n ≤ 10^5$，$1 ≤ m ≤ 10$，$1 ≤ q ≤ 10^5$），以空格分隔。

接下来的 $n$ 行，每行包含 $m$ 个字符，用于描述表格。这些字符只能是 <、^ 或 > 中的一个。

接下来的 $q$ 行，每行描述一个事件。格式为 "C x y c" 或 "A x y"（连续元素之间以空格分隔）。保证 $1 ≤ x ≤ n$，$1 ≤ y ≤ m$；$c$ 是集合 $\{<, ^, >\}$ 中的一个字符。

类型为 "C" 的查询至多有 $10000$ 个。

For each event of type "A", output two integers tx, ty in a line, separated by a space, denoting the destination of (x, y) is (tx, ty).

If there is an infinite loop, you should output tx = ty =  - 1.

对于每个类型为“A”的事件，输出一行两个整数 $t_x$ 和 $t_y$，以空格分隔，表示点 $(x, y)$ 的目的地为 $(t_x, t_y)$。

如果存在无限循环，则应输出 $t_x = t_y = -1$。

For the first sample:

If the bread goes from (2, 1), it will go out of the table at (1, 3).

After changing the conveyor belt of (1, 2) to "<", when the bread goes from (2, 1) again, it will get stuck at "><", so output is ( - 1,  - 1).

对于第一个样例：

如果面包从 (2, 1) 出发，它将在 (1, 3) 处移出桌面。

将 (1, 2) 处的传送带改为 “<” 后，当面包再次从 (2, 1) 出发时，它将在 “><” 处卡住，因此输出为 ( - 1,  - 1)。