Byteotia 的势利市民喜欢玩激光台球。台球桌是一个 $n \times m$ 的矩形。球桌的边框宽度为 $\frac{1}{4}$，包含 $n + m$ 对激光发射器。当所有发射器开启时，球桌被 $n$ 条“水平”激光束和 $m$ 条“垂直”激光束覆盖，使得第 $i$ 条水平激光束（$1 \le i \le n$）与第 $j$ 条垂直激光束（$1 \le j \le m$）在点 $(j - \frac{1}{2}, i - \frac{1}{2})$ 处相交。发射器可以独立开启或关闭。

激光台球使用直径为 $\frac{1}{2}$ 的球进行游戏。当球穿过至少一条激光束时，会显示命中信号。

初始时，球位于点 $(x - \frac{1}{2}, y - \frac{1}{2})$。球被球杆击中，其初始速度向量为 $(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$ 行：对应每个查询的答案。每个答案应为一个整数：命中信号显示的次数。

样例

输入 1

4 6
1010
010110
1
5 2 1 1 8

输出 1

6