Bitsets

Consider the following operations on bitsets of size $m$:

• $c = a\,\mathrm{and}\,b$: $c_i=1$ if both $a_i$ and $b_i$ are 1. Otherwise, $c_i=0$.
• $c = a\,\mathrm{or}\,b$: $c_i=1$ if at least one of $a_i$ and $b_i$ is 1. Otherwise, $c_i=0$.
• $c = a\,\mathrm{xor}\,b$: $c_i=1$ if exactly one of $a_i$ and $b_i$ is 1. Otherwise, $c_i=0$.
• $c = \mathrm{not}\,a$: $c_i=1$ if $a_i$ is 0. Otherwise, $c_i=0$.

You are given an array of bitsets $s_1, s_2, \ldots, s_n$. Write a program that answers $k$ queries of the following form:

1. Read two integers $\ell$ and $r$.
2. Compute the bitset $t = (s_\ell \,\mathrm{and}\, s_{\ell+1} \,\mathrm{and}\, \ldots \,\mathrm{and}\, s_r) \,\mathrm{xor}\, (\mathrm{not}\, (s_\ell \,\mathrm{or}\, s_{\ell+1} \,\mathrm{or}\, \ldots \,\mathrm{or}\, s_r))$.
3. Count the number of ones in $t$. This count is the answer.

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$; $n \cdot m \leq 10^6$). Each of the following $n$ lines contains a bitset of $m$ characters, each 0 or 1.

The next line contains the number of queries $k$ ($1 \leq k \leq 2 \cdot 10^7$). The following line contains three integers $x$, $y$, and $z$ ($1 \leq x, y, z \leq 10^9$).

The queries are generated from $x$, $y$, $z$ and the answers $q_1, q_2, \ldots, q_{k-1}$ to the previous queries. Define the sequences $a$ and $b$ as follows:

• $a_1 = 1$.
• $b_1 = n$.
• For $i > 1$, $a_i = (a_{i-1} \cdot x + q_{i-1} \cdot y + z) \bmod n + 1$.
• For $i > 1$, $b_i = (b_{i-1} \cdot y + q_{i-1} \cdot z + x) \bmod n + 1$.

For query $i$, let $\ell = \min(a_i, b_i)$ and $r = \max(a_i, b_i)$.

Output a single integer: the sum of the answers to all queries.

The queries are listed below: