爱丽丝、鲍勃与两个数组

时间与内存限制

• 时间限制：$2.5$ 秒
• 内存限制：$1024$ MB

题意翻译

有一个长度为 $N$ 的数组 $a$ 和一个长度为 $M$ 的数组 $b$。 数组中所有数字都是整数，且范围在 $1$ 到 $k$ 之间。 另有一个初始为空的数组 $c$。

爱丽丝和鲍勃在这些数组上玩如下游戏： 玩家轮流操作，轮到的玩家必须向 $c$ 的末尾添加一个数字，使得 $c$ 始终是 $a$ 和 $b$ 的公共子序列。 无法操作的玩家输掉游戏。爱丽丝先手。

他们会进行 $q$ 局游戏。 第 $i$ 局游戏流程：

1. 选择两个数 $x_i, y_i$（$0 \le x_i < N, 0 \le y_i < M$）。
2. 从 $a$ 中删除前 $x_i$ 个元素，从 $b$ 中删除前 $y_i$ 个元素。
3. 在剩余的数组上进行游戏。
4. 每局结束后，$a,b$ 恢复为初始状态，$c$ 清空。

题目保证：每局删除后，剩余的 $a$ 和 $b$ 开头数字一定相同。

请你对每局游戏判断：如果双方都采取最优策略，爱丽丝是否必胜？

---

输入格式

第一行六个整数： $N, n, M, m, k, q$ 其中：

• $N$：数组 $a$ 长度
• $n$：$a$ 的连续段数量
• $M$：数组 $b$ 长度
• $m$：$b$ 的连续段数量
• $k$：数字值域上限
• $q$：游戏局数

限制： $1 \le N,M \le 10^9$ $1 \le n,m,k \le 1600$ $1 \le q \le 10^6$

接下来 $n$ 行描述数组 $a$ 的连续段： 每行两个整数 $la_i, va_i$ 表示一段长度为 $la_i$、数字全为 $va_i$ 的段。 保证 $\sum la_i = N$，且相邻段数字不同。

接下来 $m$ 行描述数组 $b$ 的连续段，格式同上。

接下来 $q$ 行，每行一对整数 $x_i, y_i$，表示一局游戏。

---

输出格式

对于每局游戏：

• 爱丽丝必胜：输出 Yes
• 鲍勃必胜：输出 No

---

样例输入

5 1 5 1 1 9
5 1
5 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

样例输出

Yes
No
Yes
No
No
Yes
Yes
Yes
Yes

---

样例解释（第一组）

$a = [1,1,1,1,1],\ b = [1,1,1,1,1]$。

• 第一局：$x=0,y=0$ 可以添加 $5$ 次 $1$，共 $5$ 步。 先手（爱丽丝）走第 $1,3,5$ 步，最后鲍勃无法操作，爱丽丝胜。

• 第二局：$x=0,y=1$ 剩余长度 $4$，共 $4$ 步。 后手必胜，输出 No。

---