说明

:::epigraph 从炮火中逃脱后，巨龙 Evirir 已精疲力竭，这次写不出花絮了。 :::

给定一个正整数 $M$。有两个非负整数列表 $A_0$ 和 $A_1$，列表中的所有整数都在 $0$ 到 $M$（包含端点）之间。

你可以执行零次或多次以下操作：

• 选择一个列表 $A_i$（$i = 0$ 或 $1$），并选择 $A_i$ 中的一个整数 $x$。从 $A_i$ 中移除（一个）$x$，并向 $A_{1-i}$（即另一个列表）中插入（一个）$M-x$。

此外，在全部操作结束后，$A_0$ 和 $A_1$ 必须非空。 列表在操作过程中可以变为空，但在 全部 操作结束后，两个列表都必须非空。

你想知道是否可以通过执行这些操作，使得每个列表中的最大值都等于某个特定值。你还想知道，如果添加或删除整数，答案是否会改变。

按顺序处理 $Q$ 个查询，每个查询为以下形式之一：

• 类型 1 查询： $1\ i\ x$
  • 向 $A_i$ 中添加（一个）$x$。
• 类型 2 查询： $2\ i\ x$
  • 从 $A_i$ 中移除（一个）$x$。
• 类型 3 查询： $3\ c_0\ c_1$
  • 回答下列问题：是否可以在执行零次或多次操作$^1$后，使得 $\max(A_0) = c_0$ 且 $\max(A_1) = c_1$？在一行中输出 $\tt{YES}$ 或 $\tt{NO}$。

注意：对于类型 3 查询，你 实际上并不执行任何操作；你只需判断是否可能。

$^1$这里，$\max(A_i)$ 表示 $A_i$ 中最大的整数。

输入格式

输入的第一行包含三个以空格分隔的整数 $N_0$、$N_1$ 和 $M$（$0 \le N_0, N_1 \le 2 \cdot 10^5$，$N_0 + N_1 \le 2 \cdot 10^5$，$0 \le M \le 10^9$），其中 $N_0$ 和 $N_1$ 分别是 $A_0$ 和 $A_1$ 的长度。

第二行包含 $N_0$ 个整数，即 $A_0$ 的元素。对于 $A_0$ 中的每个整数 $x$，有 $0 \le x \le M$。若 $N_0 = 0$，则该行为空行。

第三行包含 $N_1$ 个整数，即 $A_1$ 的元素。对于 $A_1$ 中的每个整数 $x$，有 $0 \le x \le M$。若 $N_1 = 0$，则该行为空行。

第四行包含一个整数 $Q$（$1 \le Q \le 2 \cdot 10^5$），表示查询的数量。

接下来的 $Q$ 行按顺序包含查询。每个查询由三个以空格分隔的整数组成，为以下形式之一：

• $1\ i\ x$（$i = 0$ 或 $1$，$0 \le x \le M$）
• $2\ i\ x$（$i = 0$ 或 $1$，$0 \le x \le M$）
  • 保证在执行此查询时，$A_i$ 中包含 $x$。
• $3\ c_0\ c_1$（$0 \le c_0, c_1 \le M$）
  • 保证在执行此查询时，$A_0$ 和 $A_1$ 中的整数总数至少为 $2$。

保证至少有一个类型 3 查询。

输出格式

对于按顺序给出的每个类型 3 查询，如果答案为是，则在一行中输出 $\tt{YES}$，否则输出 $\tt{NO}$。

你可以以任意大小写输出 $\tt{YES}$ 和 $\tt{NO}$ 中的每个字母。例如，$\tt{yes}$ 和 $\tt{yEs}$ 将被视为 $\tt{YES}$；$\tt{no}$ 和 $\tt{No}$ 将被视为 $\tt{NO}$。

5 4 10
3 4 6 7 0
1 3 7 8
11
3 7 3
3 0 1
3 6 9
3 4 4
3 7 8
2 1 3
1 0 5
1 1 2
3 4 4
3 0 10
3 7 5

YES
NO
NO
YES
YES
NO
NO
YES

10 0 8
2 2 3 3 3 1 5 5 5 6
4
3 2 6
3 6 2
3 5 3
3 3 5

YES
NO
YES
YES

0 0 10
5
1 1 4
1 1 6
2 1 4
1 0 4
3 4 6

YES

提示

注释

示例 1

对于第一个查询（$\tt{3 7 3}$），我们可以执行以下操作：

• 从 $A_1$ 中选择 8：从 $A_1$ 中移除 8，并向 $A_0$ 中插入 $10 - 8 = 2$。
• 从 $A_1$ 中选择 7：从 $A_1$ 中移除 8，并向 $A_0$ 中插入 $10 - 7 = 3$。

操作后得到 $A_0 = [3, 4, 6, 7, 0, 2, 3]$ 和 $A_1 = [1, 3]$。$A_0$ 和 $A_1$ 中的最大元素分别如愿变为 7 和 3，因此答案为 $\tt{YES}$。

对于第四个查询（$\tt{3 4 4}$），我们可以对 $A_0$ 中的 6 和 7，以及 $A_1$ 中的 7 和 8 进行操作。操作后得到 $A_0 = [3, 4, 0, 3, 2]$ 和 $A_1 = [1, 3, 4, 3]$。

对于第五个查询（$\tt{3 7 8}$），$A_0$ 和 $A_1$ 中的最大元素已经是 7 和 8，因此无需操作。

在第六个查询（$\tt{2 1 3}$）之后，$A_1 = [1, 7, 8]$。在第七和第八个查询（$\tt{1 0 5}$ 和 $\tt{1 1 2}$）之后，$A_0 = [3, 4, 6, 7, 0, 5]$，$A_1 = [1, 7, 8, 2]$。

示例 2

此示例满足子任务 1 和子任务 2 的约束。对于第一个查询，我们可以移除 $A_0$ 中的一个 2，并向 $A_1$ 中插入 $8 - 2 = 6$。

示例 3

注意，初始时两个列表都可以为空。

计分

子任务 1 （$17$ 分）： $N_0, M, Q \le 100$。$N_1 = 0$。所有查询均为类型 3 查询，且满足 $c_0 = M - c_1$。

子任务 2 （$9$ 分）： $N_1 = 0$。所有查询均为类型 3 查询，且满足 $c_0 = M - c_1$。

子任务 3 （$14$ 分）： $M \le 2$。所有查询均为类型 3 查询。

子任务 4 （$28$ 分）： $N_0 + N_1 \le 2000$，$Q \le 2000$。所有查询均为类型 3 查询。

子任务 5 （$21$ 分）： 所有查询均为类型 3 查询。

子任务 6 （$11$ 分）： 无额外限制。

翻译由 DeepSeek 完成