Cossack Vus and the Table#10487
Cossack Vus recently discovered a table with rows and columns. This matrix is filled with the symbols , , , and .
Cossack Vus has defined rules for moving through the matrix. If you are currently at cell (the cell at the intersection of the -th row and the -th column), then:
If a_{i j}='<', move to cell (x, y-1);
If a_{i j}='>', move to cell (x, y+1);
If a_{i j}=\text{'v'}, move to cell (x+1, y);
If a_{i j}=\text{'\textasciicircum'}, move to cell (x-1, y).
The path ends when you move outside the boundaries of the matrix.
Cossack Vus has prepared queries for you, each in the form x_s \ \ y_s \ \ x \ y \ c. He wants to know how many cells you will pass through to exit the matrix if you start at cell (x_s, y_s). Before starting, you must change the element a_{x y} to .
Note that these queries are independent. Any changes made for a query revert back before the next query.
The first line contains two integers and (1 \le n, m \le 1500) — the number of rows and columns, respectively.
The next lines contain the elements of each row of the matrix: a_{i 1}, a_{i 2}, \dots, a_{i m}, without spaces between them.
The following line contains one integer (1 \le q \le 10^5) — the number of queries.
Each of the next lines describes a query in the form x_s \ \ y_s \ \ x \ y \ c (1 \le x_s, x \le n, 1 \le y_s, y \le m, c \in \{\text{'<'}, \text{'>'}, \text{'\textasciicircum'}, \text{'v'}\}).
For each query, output a single integer on a separate line — the number of cells you need to pass through to exit the matrix starting from cell (x_s, y_s). If you never exit the matrix, output «0».
Example 1
( points): n, m \le 100, q \le 1000;
( points): initially, it is not possible to exit the matrix from any cell;
( points): n, m \le 300, initially, it is possible to exit the matrix from any cell;
( points): n, m \le 300;
( points): initially, it is possible to exit the matrix from any cell;
( points): no additional constraints.