A bitset of size $m$ is defined as a boolean array of length $m$.

The following four operations are defined for bitsets of size $m$:

• $c = a \text{ and } b$: Here, $c_i = 1$ if $a_i = 1$ and $b_i = 1$; otherwise, $c_i = 0$.
• $c = a \text{ or } b$: Here, $c_i = 1$ if $a_i = 1$ or $b_i = 1$; otherwise, $c_i = 0$.
• $c = a \text{ xor } b$: Here, $c_i = 1$ if exactly one of $a_i$ and $b_i$ is $1$; otherwise, $c_i = 0$.
• $c = \text{not } a$: Here, $c_i = 1$ if $a_i = 0$; otherwise, $c_i = 0$.

Given an array of $n$ bitsets $s_1, s_2, \dots, s_n$, write a program to answer $k$ queries. Each query provides $l$ and $r$, and you need to calculate $t$ using the following formula:

• $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))$

Find the number of $1$s in $t$.

Input

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$; $n \cdot m \leq 10^6$). The next $n$ lines describe the $n$ bitsets, where each line consists of $m$ zeros or ones, representing a bitset.

The next line contains an integer $k$, representing the number of queries ($1 \leq k \leq 2 \times 10^6$).

The next line contains three integers $x, y, z$ ($1 \leq x, y, z \leq 10^9$).

The queries are generated by a pseudo-random algorithm using $x, y, z$ as parameters. Specifically, consider generating sequences $a$ and $b$ of length $k$:

• $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$.

Where $l$ for the $i$-th query is $\min\{a_i, b_i\}$ and $r$ is $\max\{a_i, b_i\}$, and $q_{i-1}$ in the formula denotes the answer to the $(i-1)$-th query.

Output

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

Examples

Input 1

4 10
1010110101
0101111001
1101101101
1011010000
4
10 5 4

Output 1

9

Note

Query 1: $l=1, r=4$, answer is 1. Query 2: $l=3, r=4$, answer is 3. Query 3: $l=2, r=4$, answer is 2. Query 4: $l=1, r=3$, answer is 3.