비트셋

크기가 $m$인 비트셋에 대해 다음 연산을 정의합니다.

• $c = a\,\mathrm{and}\,b$: $a_i$와 $b_i$가 모두 1이면 $c_i=1$이고, 그렇지 않으면 $c_i=0$입니다.
• $c = a\,\mathrm{or}\,b$: $a_i$와 $b_i$ 중 하나라도 1이면 $c_i=1$이고, 그렇지 않으면 $c_i=0$입니다.
• $c = a\,\mathrm{xor}\,b$: $a_i$와 $b_i$ 중 정확히 하나만 1이면 $c_i=1$이고, 그렇지 않으면 $c_i=0$입니다.
• $c = \mathrm{not}\,a$: $a_i$가 0이면 $c_i=1$이고, 그렇지 않으면 $c_i=0$입니다.

비트셋 배열 $s_1, s_2, \ldots, s_n$이 주어집니다. 다음 형태의 질의 $k$개에 답하는 프로그램을 작성하세요.

1. 정수 $\ell$과 $r$을 입력받습니다.
2. 다음 식으로 비트셋 $t$를 구합니다. $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. $t$에서 1의 개수를 셉니다. 이 값이 질의의 답입니다.

첫 줄에 정수 $n$과 $m$이 주어집니다 ($1 \leq n, m \leq 10^5$; $n \cdot m \leq 10^6$). 다음 $n$개의 줄은 각각 $m$개의 문자 0과 1로 이루어진 비트셋을 나타냅니다.

다음 줄에는 질의 수 $k$ ($1 \leq k \leq 2 \cdot 10^7$)가 주어집니다. 그다음 줄에는 정수 $x$, $y$, $z$ ($1 \leq x, y, z \leq 10^9$)가 주어집니다.

질의는 $x$, $y$, $z$와 이전 질의의 답 $q_1, q_2, \ldots, q_{k-1}$을 이용해 생성됩니다. 수열 $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$번째 질의에서 $\ell = \min(a_i, b_i)$, $r = \max(a_i, b_i)$입니다.

모든 질의 답의 합을 정수 하나로 출력합니다.

질의 목록은 다음과 같습니다.