1247 : 四国军棋

Description

四国军棋是一款有趣的桌游。这里我们考虑一个简化的版本，其有两个玩家小 A 和小 B，棋子是 \([1, 10^5]\) 内的整数。游戏过程如下：

• 初始，小 A 有 \(n_1\) 个棋子，构成序列 \(A\)；小 B 有 \(n_2\) 个棋子，构成序列 \(B\)。\(A\) 和 \(B\) 均为给定的，小 A 和小 B 不能修改。
• 两人派出序列中的第一个棋子，不妨假设分别为 \(x,y\)，然后进行战斗。
  • 若 \(x>y\)，即小 A 更大，则小 B 的棋子进入弃子堆，之后无法再被使用，然后小 B 派出序列中的下一个棋子，继续进行战斗；
  • 若 \(y>x\)，即小 B 更大，则小 A 的棋子进入弃子堆，之后无法再被使用，然后小 A 派出序列中的下一个棋子，继续进行战斗；
  • 若 \(x=y\)，即双方一样大，双方的棋子都进入弃子堆，无法再被使用，双方派出序列中的下一个棋子，继续进行战斗。
• 在战斗过程中，若某一玩家需要派出棋子时没有任何剩余棋子，此时该玩家判负，另一玩家获胜。
  • 特别地，若两方都需要派出棋子但两方都没有任何剩余棋子，则判和。

你可以参考样例解释理解该游戏过程。

小 A 和小 B 是好朋友，他们不希望在游戏中分出胜负，一个平局会让他们更高兴。

给出初始的游戏局面和 \(m\) 次修改，每次修改中，某个序列中的某个棋子会被替换成其他棋子，每次修改的效果会在这次修改之后保留。

每一次修改后，他们希望你能帮他们分析出，如果按照该序列进行游戏，游戏结果是否为平局。

Input

第一行一个正整数 \(n_1\)（\(1\leq n_1\leq 10^5\)）表示小 A 的棋子个数。

第二行 \(n_1\) 个正整数 \(a_1,a_2,\dots,a_n\)（\(1 \le a_i \le 10^5\)）描述序列 \(A\)。

第三行一个正整数 \(n_2\)（\(1\leq n_2\leq 10^5\)）表示小 B 的棋子个数。

第四行 \(n_2\) 个正整数 \(b_1,b_2,\dots,b_n\)（\(1 \le b_i \le 10^5\)）描述序列 \(B\)。

第五行一个正整数 \(m\)（\(1\leq m\leq 2\times 10^5\)）描述修改个数。

之后 \(m\) 行，每行三个正整数 \(o,x,y\)（\(1\leq o\leq 2\)，\(1 \le x \le n_o\)，\(1 \le y \le 10^5\)），意义如下：

• 若 \(o=1\) 表示将 \(a_x\) 修改为 \(y\)；
• 若 \(o=2\) 表示将 \(b_x\) 修改为 \(y\)。

Output

对于每次修改输出一行，如果游戏结果为平局输出 YES，否则输出 NO。

Sample

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

NO
NO
NO
YES
NO
NO
NO
YES

Hint

【样例解释 #0】

对于第一次修改，\(A = \{5, 2, 3, 4, 5\}\)，\(B = \{5, 4, 3, 2, 1\}\)，游戏过程如下：

1. 小 A 派出 \(a_1 = 5\)，小 B 派出 \(b_1 = 5\)。
2. \(a_1 = 5 = b_1 = 5\)，都进入弃子堆，小 A 派出 \(a_2 = 2\)，小 B 派出 \(b_2 = 4\)；
3. \(a_2 = 2 < b_2 = 4\)，\(a_2\) 进入弃子堆，小 A 派出 \(a_3 = 3\)；
4. \(a_3 = 3 < b_2 = 4\)，\(a_3\) 进入弃子堆，小 A 派出 \(a_4 = 4\)；
5. \(a_4 = 4 = b_2 = 4\)，都进入弃子堆，小 A 派出 \(a_5 = 5\)，小 B 派出 \(b_3 = 3\)；
6. \(a_5 = 5 > b_3 = 3\)，\(b_3\) 进入弃子堆，小 B 派出 \(b_4 = 2\)；
7. \(a_5 = 5 > b_4 = 2\)，\(b_4\) 进入弃子堆，小 B 派出 \(b_5 = 1\)；
8. \(a_5 = 5 > b_5 = 1\)，\(b_5\) 进入弃子堆，小 B 需要派出棋子但没有棋子，因此结果不是平局，输出 NO。

对于最后一次修改，\(A = \{5, 4, 3, 2, 5\}\)，\(B = \{4, 4, 5, 2, 5\}\)，游戏过程如下：

1. 小 A 派出 \(a_1 = 5\)，小 B 派出 \(b_1 = 4\)。
2. \(a_1 = 5 > b_1 = 4\)，\(b_1\) 进入弃子堆，小 B 派出 \(b_2 = 4\)；
3. \(a_1 = 5 > b_2 = 4\)，\(b_2\) 进入弃子堆，小 B 派出 \(b_3 = 5\)；
4. \(a_1 = 5 = b_3 = 5\)，都进入弃子堆，小 A 派出 \(a_2 = 4\)，小 B 派出 \(b_4 = 2\)；
5. \(a_2 = 4 > b_4 = 2\)，\(b_4\) 进入弃子堆，小 B 派出 \(b_5 = 5\)；
6. \(a_2 = 4 < b_5 = 5\)，\(a_2\) 进入弃子堆，小 A 派出 \(a_3 = 3\)；
7. \(a_3 = 3 < b_5 = 5\)，\(a_3\) 进入弃子堆，小 A 派出 \(a_4 = 2\)；
8. \(a_4 = 2 < b_5 = 5\)，\(a_4\) 进入弃子堆，小 A 派出 \(a_5 = 5\)；
9. \(a_5 = 5 = b_5 = 5\)，都进入弃子堆，双方需要派出棋子且都没有棋子，因此结果为平局，输出 YES。

Source

Author

THU