Conveyor Belts

题意翻译

有一个$ n×m $的地图，上面有三种符号'<^>' 分别表示向左，向上，向右 有两种操作，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 $次

题目描述

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.

输入输出格式

输入格式

The first line of input contains three integers $ n $ , $ m $ and $ q $ ( $ 1<=n<=10^{5},1<=m<=10,1<=q<=10^{5} $ ), 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.

输出格式

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 $ .

输入输出样例

输入样例 #1

2 2 3
>>
^^
A 2 1
C 1 2 <
A 2 1

输出样例 #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

输出样例 #2

0 4
-1 -1
-1 -1
0 2
0 2

说明

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) $ .