题目描述

定义大小为 $m$ 的 bitset 为长度为 $m$ 的 bool 数组。

对大小为 $m$ 的 bitset 定义如下四种运算：

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

给定大小为 $n$ 的 bitset 数组 $s_1, s_2, \ldots, s_n$，编写程序回答 $k$ 个查询。每次查询给定 $l, r$，需计算： $t = (s_l \text{ and } s_{l+1} \text{ and } \ldots \text{ and } s_r) \text{ xor } (\text{not } (s_l \text{ or } s_{l+1} \text{ or } \ldots \text{ or } s_r))$ 求 $t$ 中 $1$ 的个数。

输入格式

第一行包含整数 $n$ 和 $m$（$1 < n, m \leq 10^5$，$n \cdot m \leq 10^6$）。
接下来 $n$ 行，每行 $m$ 个 $0/1$ 字符表示一个 bitset。
然后一行 $k$（查询数量，$1 \leq k \leq 2 \times 10^6$）。
最后一行三个整数 $x, y, z$（$1 \leq x, y, z \leq 10^9$）。

查询是通过以$x, y, z$为参数的伪随机算法生成的，具体来说，考虑生成长度为$k$的序列$a, b$：

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

其中，第$i$个询问的$l$是 $\min(a_i, b_i)$，$r$是 $\max(a_i, b_i)$，公式里的$q_{i-1}$表示第$i-1$个询问的答案。

输出格式

输出所有查询答案的总和。

样例1

输入

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

输出

9

样例解释

对于询问 $1:$ $l = 1, r = 4,$ 答案为 $1$;

对于询问 $2:$ $l = 3, r = 4,$ 答案为 $3$;

对于询问 $3:$ $l = 2, r = 4,$ 答案为 $2$;

对于询问 $4:$ $l = 1, r = 3,$ 答案为 $3$;

数据范围与约定

• $1 < n, m \leq 10^5$，$n \cdot m \leq 10^6$
• $1 \leq k \leq 2 \times 10^6$
• $1 \leq x, y, z \leq 10^9$

子任务