P5652 基础博弈练习题

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$ 轮游戏，给出每轮游戏使用的区间，请你判断每轮谁会赢。

无

无

对于 $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$。