Geometry Quota

There is an $N \times M$ grid. Each cell is either empty or an obstacle.

Let the bottom-left corner of the grid be $(0,0)$ and the top-right corner be $(M,N)$. Every grid point has integer coordinates.

You are given $Q$ queries. Each query gives two distinct grid points $(x_1,y_1)$ and $(x_2,y_2)$.

Find the number of obstacle cells whose interior is crossed by the line segment joining the two points. If the segment only touches an edge or a corner of an obstacle cell without passing through its interior, that cell is not counted.

The input is given in the following format.

$N\ M\ Q$ $S_1$ $S_2$

For each query, print the number of obstacle cells whose interior is crossed by the segment on its own line.

• $1 \le NM \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $$ is a string of length consisting only of and . ()