Cossack Vus and the Table

Cossack Vus recently discovered a table $a$ with $n$ rows and $m$ columns. This matrix is filled with the symbols $\text{’<’}$, $\text{’>’}$, $\text{’^’}$, and $\text{’v’}$.

Cossack Vus has defined rules for moving through the matrix. If you are currently at cell $(x,y)$ (the cell at the intersection of the $x$-th row and the $y$-th column), then:

• If $a_{ij}{=}^{\prime }{<}^{\prime }$, move to cell $(x,y-1)$;

• If $a_{ij}{=}^{\prime }{>}^{\prime }$, move to cell $(x,y+1)$;

• If $a_{ij}=\text{’v’}$, move to cell $(x+1,y)$;

• If $a_{ij}=\text{’^’}$, move to cell $(x-1,y)$.

The path ends when you move outside the boundaries of the matrix.

Cossack Vus has prepared $q$ queries for you, each in the form $x_s{y}_{s}xyc$. 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_{xy}$ to $c$.

Note that these queries are independent. Any changes made for a query revert back before the next query.

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 1500$) — the number of rows and columns, respectively.

The next $n$ lines contain the elements of each row of the matrix: $a_{i1},a_{i2},\dots ,a_{im}$, without spaces between them.

The following line contains one integer $q$ ($1\le q\le 10^5$) — the number of queries.

Each of the next $q$ lines describes a query in the form $x_s{y}_{s}xyc$ ($1\le x_s,x\le n,1\le y_s,y\le m,c\in \{\text{’<’},\text{’>’},\text{’^’},\text{’v’}\}$).

Output

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

Examples

Scoring

1. ($13$ points): $n,m\le 100,q\le 1000$;

2. ($13$ points): initially, it is not possible to exit the matrix from any cell;

3. ($18$ points): $n,m\le 300$, initially, it is possible to exit the matrix from any cell;

4. ($12$ points): $n,m\le 300$;

5. ($30$ points): initially, it is possible to exit the matrix from any cell;

6. ($14$ points): no additional constraints.