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
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
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
The input starts with $3$ positive integers $M$, $N$ and $Q$ $(M \times N \leq 100\, 000, Q \leq 100\,
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)$.
The next $Q$ lines
describe $Q$ queries.
Each query belongs to one of the two types:
$x$ $y$ $(1 \leq x \leq M, \; 1 \leq y \leq
N)$ - flip the wall at cell $(i,j)$.
$y$ $(1 \leq y \leq N)$ - drop the
ball at column $y$.
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
|Sample Input 1
||Sample Output 1
4 4 7
1 4 2
1 4 4