题目描述

定义大小为 $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_i$ 和 $b_i$ 中恰好有一个为 $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, \dots, s_n$，编写程序来回答 $k$ 个查询，每次查询给定 $l,r$，你需要使用以下公式计算 $t$：

• $t=(s_l \space \text{and}\space s_{l+1} \space \text{and } \cdots \text{ and } s_r) \text{ xor } (\text{not }(s_l \text{ or } s_{l+1} \text{ or } \cdots \text{ or } s_r))$

求 $t$ 中 1 的个数。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 10^5$; $n \cdot m \leq 10^6$)。接下来的 $n$ 行描述了 $n$ 个 bitset，每行由 $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) \bmod n + 1$。
• 对于 $i > 1$，$b_i = (b_{i-1} \cdot y + q_{i-1} \cdot z + x) \bmod 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

样例输出 1

9

样例输入/输出 2~3

见下发文件。

样例解释

数据范围与约定

对于所有数据，有：

• $1 \le n,m \le 10^5$
• $nm \le 10^6$
• $1 \le k \le 2 \times 10^6$
• $1 \le x,y,z \le 10^9$

子任务：