Description

YSGH and YGSH are playing “ge mo” (pinyin: gémó), and YSGS is watching.

The rules are as follows. First, a positive integer $m$ and a sequence $b$ of $n$ numbers are given. Initially, there is a piece on the first position of $b$, and $b_1$ is decreased by $1$. After that, the two players take turns. On each move, suppose the current piece is at position $i$. The player may move the piece to a position $j$ such that $j \in [i, \min(i + m, n)]$ and $b_j > 0$, then decrease $b_j$ by $1$. YSGH moves first. Whoever cannot make a move loses.

It is well known that both YSGH and YGSH are extremely smart, so both will use optimal strategies.

The sequence $b$ used in “ge mo” is a non-empty contiguous subsequence of a sequence $a$. Of course, both the sequence $a$ and the sequence $b$ used in each round are chosen by YSGS.

Now they play $q$ rounds of the game. Given the interval used in each round, please determine who will win each round.

Input Format

Because the data size of this problem is large, direct input and output will take much more time than computation. Therefore, when there are too many queries, the input and output of the queries are compressed.

The first line contains four positive integers $n, m, q, type$. The meanings of $n, m, q$ are the same as in the statement. $type$ indicates the type of the current testdata. $type = 1$ means this testdata is compressed, and $type = 0$ means it is not. The testdata guarantees that when $q > {10}^6$, $type = 1$.

The second line contains $n$ positive integers. The $i$-th positive integer represents $a_i$, with the same meaning as in the statement.

If $type = 1$, the third line contains four positive integers $A, B, C, P$, describing how queries are generated.

int A, B, C, P;
inline int rnd() { return A = (A * B + C) % P; }

For each query, call:

l = rnd() % n + 1, r = rnd() % n + 1;

If the generated $l > r$, then you also need to swap $l, r$.

The testdata guarantees $0 \le A B < P$, $0 \le C < P$, $P (B + 1) < 2^{31} - 1$.

If $type = 0$, the next $q$ lines each contain two positive integers $l, r$, with the same meaning as in the statement.

Output Format

Let ${ans}_i$ indicate whether YSGH will win in the $i$-th query. If YSGH will win, then ${ans}_i = 1$, otherwise ${ans}_i = 0$.

Output one line with one integer, which is $\displaystyle \left( \sum_{i = 1}^{q} i^2 \cdot {ans}_i \right)\! \bmod 2^{32}$.

5 2 3 0
2 4 1 2 3
1 5
3 5
3 4

5

Hint

For $25\%$ of the testdata, $n, m, q \le 10$, $a_i \le 2$.
For $55\%$ of the testdata, $n, m, q \le 5 \times {10}^3$.
For another $15\%$ of the testdata, $n \le {10}^5$, $m \le 5$.
For $90\%$ of the testdata, $n, m, q \le {10}^6$.
For $100\%$ of the testdata, $1 \le n, m \le {10}^6$, $1 \le q \le {10}^7$, $1 \le a_i \le {10}^9$.

Translated by ChatGPT 5