题目描述

有一个 $n×m$ 的地图，上面有三种符号 <^> 分别表示向左，向上，向右。

有 $q$ 次操作：

• A X Y 询问从一个点 $(X,Y)$ 开始最终会走到哪个点或者死循环；
• C X Y ch 表示将地图上 $(X,Y)$ 的符号换成 $ch$。

数据范围 $1 \leq n \leq 10^5$，$1 \leq m \leq 10$，C 操作最多 $10000$ 次。

输入格式

第一行三个整数 $n,m,q$，$1\le n\le 10^{5},\ 1\le m\le 10,\ 1\le q\le 10^{5}$。

接下来是一个 $n\times m$ 的地图。

接下来 $q$ 行表示操作。

输出格式

对于每一个询问，在一行中输出答案。

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