33334번 - Bitsets 다국어

문제

Let us consider the following operations on bitsets of size $m$:

• $c = a,円 \mathrm{ and },円 b$. Here, $c_i=1$ if both $a_i$ and $b_i$ are equal to 1ドル$. Otherwise, $c_i=0$.
• $c = a,円 \mathrm{ or },円 b$. Here, $c_i=1$ if either $a_i$ or $b_i$ is equal to 1ドル$. Otherwise, $c_i=0$.
• $c = a,円 \mathrm{ xor },円 b$. Here, $c_i=1$ if exactly one of $a_i$ and $b_i$ is equal to 1ドル$. Otherwise, $c_i=0$.
• $c = \mathrm{ not },円 a$. Here, $c_i=1$ if $a_i$ is equal to 0ドル$. Otherwise, $c_i=0$.

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

1. Take two integers $\ell$ and $r$.
2. Find bitset $t$ using the formula: $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 bitset $t$: it 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$). The following $n$ lines describe the $n$ bitsets, where each line consists of $m$ characters 0ドル$ and 1ドル$ representing the bits of that bitset.

The next line of the input contains a single integer $k$ (1ドル \leq k \leq 2 \cdot 10^7$), which denotes the number of queries. The following line contains three integers $x,ドル $y,ドル and $z$ (1ドル \leq x, y, z \leq 10^9$).

The queries are generated using pseudo-random numbers, with input parameters $x,ドル $y,ドル and $z,ドル and a sequence $q_1, q_2, \ldots, q_{k - 1}$ of answers to the queries. Define two 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 each query $i,ドル the parameters $\ell$ and $r$ are defined as $\ell=\min(a_i, b_i)$ and $r=\max(a_i, b_i)$.

출력

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

제한

노트

The queries are listed below: