考虑以下大小为 $m$ 的位集（bitset）操作：

• $c = a \text{ and } b$。其中，若 $a_i$ 和 $b_i$ 均为 $1$，则 $c_i = 1$；否则 $c_i = 0$。
• $c = a \text{ or } b$。其中，若 $a_i$ 或 $b_i$ 为 $1$，则 $c_i = 1$；否则 $c_i = 0$。
• $c = a \text{ xor } b$。其中，若 $a_i$ 和 $b_i$ 中恰有一个为 $1$，则 $c_i = 1$；否则 $c_i = 0$。
• $c = \text{not } a$。其中，若 $a_i = 0$，则 $c_i = 1$；否则 $c_i = 0$。

给定一个位集数组 $s_1, s_2, \dots, s_n$。编写一个程序来回答 $k$ 个如下形式的询问：

1. 给定两个整数 $\ell$ 和 $r$。
2. 根据公式计算位集 $t$：$t = (s_\ell \text{ and } s_{\ell+1} \text{ and } \dots \text{ and } s_r) \text{ xor } (\text{not } (s_\ell \text{ or } s_{\ell+1} \text{ or } \dots \text{ or } s_r))$。
3. 计算位集 $t$ 中 $1$ 的个数，即为询问的答案。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5; n \cdot m \le 10^6$)。接下来的 $n$ 行描述了 $n$ 个位集，每行包含 $m$ 个字符 $0$ 或 $1$，表示该位集的位。

下一行包含一个整数 $k$ ($1 \le k \le 2 \cdot 10^7$)，表示询问次数。随后一行包含三个整数 $x, y, z$ ($1 \le x, y, z \le 10^9$)。

询问通过伪随机数生成，使用输入参数 $x, y, z$ 以及一个包含前 $k-1$ 个询问答案的序列 $q_1, q_2, \dots, q_{k-1}$。定义两个序列 $a$ 和 $b$ 如下：

• $a_1 = 1$。
• $b_1 = n$。
• 对于 $i > 1$，$a_i = (a_{i-1} \cdot x + q_{i-1} \cdot y + z) \pmod n + 1$。
• 对于 $i > 1$，$b_i = (b_{i-1} \cdot y + q_{i-1} \cdot z + x) \pmod n + 1$。

对于每个询问 $i$，参数 $\ell$ 和 $r$ 定义为 $\ell = \min(a_i, b_i)$ 且 $r = \max(a_i, b_i)$。

输出格式

输出一个整数：所有询问答案的总和。

样例

样例输入 1

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

样例输出 1

9

说明

询问列表如下：