基础博弈练习题

YSGH is our red sun.

YSGH 和 YGSH 在打膈膜，YSGS 在旁边围观。 规则是这样的，先给定一个正整数 $m$ 和一个 $n$ 个数的序列 $b$，一开始有一个棋子在 $b$ 的第一个位置，并将 $b_1$ 减去 $1$。此后双方轮流操作，每次操作，假设当前棋子在 $i$，可以把棋子移到一个位置 $j$，满足 $j \in [i, \min(i + m, n)]$ 且 $b_j > 0$，然后将 $b_j$ 减 $1$，YSGH 先手，谁先不能操作谁输。 众所周知，YSGH 和 YGSH 都是绝顶聪明的，所以两人都会使用最优策略。 而隔膜使用的序列 $b$ 是一个序列 $a$ 的一个连续非空子序列，当然序列 $a$ 和每次隔膜使用的序列 $b$ 都是 YSGS 定的。 现在他们进行了 $q$ 轮游戏，给出每轮游戏使用的区间，请你判断每轮谁会赢。

由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此当询问过多时会对询问的输入输出进行了压缩。 第一行四个正整数 $n, m, q, type$，$n, m, q$ 意义同题面描述，$type$ 表示当前数据的类型，$type = 1$ 说明该组数据进行了压缩，$type = 0$ 则说明没有，数据保证当 $q > {10}^6$ 时，$type=1$。 第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$，意义同题面描述。 如果 $type = 1$，第三行四个正整数 $A, B, C, P$，表示询问的生成方式。 ```cpp int A, B, C, P; inline int rnd() { return A = (A * B + C) % P; } ``` 每次询问时的调用方法为： ```cpp l = rnd() % n + 1, r = rnd() % n + 1; ``` 如果生成的 $l > r$，则还需要交换 $l, r$。 数据保证 $0 \le A B < P$，$0 \le C < P$，$P (B + 1) < 2^{31} - 1$。 如果 $type=0$，接下来 $q$ 行，每行两个正整数 $l, r$，意义同题面描述。

令 ${ans}_i$ 表示第 $i$ 次询问中 YSGH 是否会赢，如果会赢则 ${ans}_i = 1$，否则 ${ans}_i = 0$。 输出一行一个整数，表示 $\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

对于 $25\%$ 的数据，$n, m, q \le 10$，$a_i \le 2$。 对于 $55\%$ 的数据，$n, m, q \le 5 \times {10}^3$。 另有 $15\%$ 的数据，$n \le {10}^5$，$m \le 5$。 对于 $90\%$ 的数据，$n, m, q \le {10}^6$。 对于 $100\%$ 的数据，$1 \le n, m \le {10}^6$，$1 \le q \le {10}^7$，$1 \le a_i \le {10}^9$。