Conveyor Belts

3000ms

262144K

Description:

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.

Input:

The first line of input contains three integers n, m and q (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10, 1 ≤ q ≤ 10⁵), 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.

Output:

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.

Sample Input:

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

Sample Output:

1 3
-1 -1

Sample Input:

4 5 7
><<^<
^<^^>
>>>^>
>^>>^
A 3 1
A 2 2
C 1 4 <
A 3 1
C 1 2 ^
A 3 1
A 2 2

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF487D