Problem E
Dropping Ball

You are given a board with $M$ rows and $N$ columns. The rows are numbered from $1$ to $M$ from top to bottom. The columns are numbered from $1$ to $N$ from left to right.

In each cell of the board, there is a diagonal wall. The wall either runs from top-left corner to bottom-right corner, or runs from top-right corner to bottom-left corner.

If you drop a ball at some column at the first row, the ball will fall downward due to gravity. Since the ball cannot go through the diagonal walls, it will travel inside the board, and the ball can have one of the following outcomes:

• The ball is stuck inside the board.

• The ball exits the board from the left edge.

• The ball exits the board from the right edge.

• The ball exits the board at the bottom edge.

For example, if we drop a ball at column $4$, the ball will exit the board from the right edge:

If we drop a ball at column $1$, the ball will exit the board at the bottom edge, at column $3$.

In this problem, we are interested in the question: “If we drop the ball at the top of column $x$, will the ball exit the board at the bottom edge? If it does, at which column of the bottom edge?”.

Those questions look easy but there is also a twist. We can flip the wall to change the direction from direction ‘\’ to direction ‘/’ or vice versa. For example, if we flip the wall at cell $(4, 2)$, the board will look like as below:

After that, if we drop the ball again at column $1$, the ball will exit the board at the bottom edge of column $1$.

Given $Q$ queries: flip-the-wall or drop-the-ball, your task is to answer all the drop-the-ball questions.

Input

• The input starts with $3$ positive integers $M$, $N$ and $Q$ $(M \times N \leq 100\, 000, Q \leq 100\, 000)$.

• The next $M$ lines, each contains a string of length $N$ describes the initial board. The $j$-th character in the $i$-th line indicate the wall direction in cell $(i, j)$.

  • ‘\’ indicates top-left to bottom-right direction,

  • ‘/’ indicates top-right to bottom-left direction.

• The next $Q$ lines describe $Q$ queries. Each query belongs to one of the two types:

  • $1$ $x$ $y$ $(1 \leq x \leq M, \; 1 \leq y \leq N)$ - flip the wall at cell $(i,j)$.

  • $2$ $y$ $(1 \leq y \leq N)$ - drop the ball at column $y$.

Output

For each query of type $2$:

• Print $-1$ if the ball can not exit at the bottom edge,

• Otherwise, print the index of the column where the ball exits.

4 4 7
\\\\
////
\\\\
/\\\
2 4
2 1
1 4 2
2 1
2 2
1 4 4
2 2

-1
3
1
4
-1