레이저 당구

바이토티아 사람들은 레이저 당구라는 놀이를 즐긴다. 당구대는 $n \times m$ 크기의 직사각형이다. 테두리(쿠션)의 폭은 $\tfrac{1}{4}$이며, 그 위에 $n + m$쌍의 레이저 송신기가 놓여 있다. 모든 송신기를 켜면 당구대는 $n$개의 가로 레이저와 $m$개의 세로 레이저로 덮이는데, $i$번째 가로 레이저($1 \le i \le n$)와 $j$번째 세로 레이저($1 \le j \le m$)는 점 $\left(j - \tfrac{1}{2},\ i - \tfrac{1}{2}\right)$에서 만난다. 각 송신기는 서로 독립적으로 켜거나 끌 수 있다.

이 놀이에는 지름이 $\tfrac{1}{2}$인 공을 사용한다. 공이 켜져 있는 레이저 중 하나 이상에 닿을 때마다 신호가 한 번 표시된다. 같은 순간에 여러 레이저에 동시에 닿더라도 신호는 한 번으로 센다.

처음에 공의 중심은 점 $\left(x - \tfrac{1}{2},\ y - \tfrac{1}{2}\right)$에 있다. 공을 쳐서 초기 속도 벡터가 $(x_v, y_v)$가 되도록 했고, 공은 마찰 없이 $t$ 시간 단위 동안 굴러간다. 쿠션과의 충돌은 모두 완전 탄성 충돌이다. 공이 움직이기 시작하는 처음 순간까지 포함하여, 신호는 모두 몇 번 표시되는가?

첫째 줄에 당구대의 크기를 나타내는 두 정수 $n$과 $m$이 주어진다 ($3 \le n, m \le 100\,000$).

둘째 줄에는 $0$과 $1$로 이루어진 $n$글자의 문자열이 주어진다. $i$번째 글자는 $i$번째 가로 송신기의 상태이며, $0$은 꺼짐, $1$은 켜짐을 뜻한다.

셋째 줄에는 세로 송신기의 상태를 같은 방식으로 나타내는 $m$글자의 문자열이 주어진다.

넷째 줄에는 질의의 개수를 나타내는 정수 $k$가 주어진다 ($1 \le k \le 10\,000$). 이어지는 $k$개의 줄에는 각각 다섯 정수 $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$). 이는 공의 시작 위치, 속도, 그리고 굴러가는 시간을 나타낸다.

정확히 $k$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의에 대한 답, 즉 신호가 표시된 횟수를 정수 하나로 출력한다.