Laser Pool

The people of Byteotia love a game called laser pool. The table is an $n \times m$ rectangle. Its rails are $\tfrac{1}{4}$ wide and hold $n + m$ pairs of laser transmitters. When every transmitter is switched on, the table is covered by $n$ horizontal and $m$ vertical laser beams, arranged so that the $i$-th horizontal beam (for $1 \le i \le n$) meets the $j$-th vertical beam (for $1 \le j \le m$) at the point $\left(j - \tfrac{1}{2},\ i - \tfrac{1}{2}\right)$. Each transmitter can be turned on or off independently.

The game uses a ball of diameter $\tfrac{1}{2}$. Whenever the ball touches at least one lit laser beam, a single hit signal is shown; touching several beams at the very same instant still counts as one signal.

At the start the ball is centered at $\left(x - \tfrac{1}{2},\ y - \tfrac{1}{2}\right)$. It is struck so that its initial velocity vector is $(x_v, y_v)$, and it then rolls without friction for $t$ units of time. Every collision with a rail is perfectly elastic. How many times is the hit signal shown, counting the initial moment of the ball's motion as well?

The first line contains two integers $n$ and $m$ ($3 \le n, m \le 100\,000$), the dimensions of the table.

The second line is a string of $n$ characters, each either $0$ or $1$. Its $i$-th character is the state of the $i$-th horizontal transmitter, where $0$ means off and $1$ means on.

The third line is a string of $m$ characters describing the vertical transmitters in the same way.

The fourth line contains an integer $k$ ($1 \le k \le 10\,000$), the number of queries. Each of the next $k$ lines contains five integers $x$, $y$, $x_v$, $y_v$, $t$ ($1 < x < m$, $1 < y < n$, $x_v, y_v \in \{-1, 1\}$, $1 \le t \le 10^9$): the starting position of the ball, its velocity, and how long it rolls.

Print exactly $k$ lines. The $i$-th line must contain one integer: the number of times the hit signal is shown for the $i$-th query.