#P18531. Quad Kingdoms Chess

Quad Kingdoms Chess

Quad Kingdoms Chess

四国军棋是一种有趣的棋类游戏。本题考虑一个简化版本,只有玩家 A、B 两人,棋子为 [1,105][1,10^5] 中的整数。对局过程如下:

  • 最初,A 有 n1n_1 枚棋子,按顺序组成序列 AA;B 有 n2n_2 枚棋子,按顺序组成序列 BB。当前局面的两个序列已经给定,对局中双方都不能改变它们。
  • 双方先分别派出序列中的第一枚棋子,设数值为 x,yx,y,进行战斗。
    • 若 x>yx>y,B 的棋子进入弃子堆,此后不能再使用。A 的当前棋子留下,B 派出序列中的下一枚棋子继续战斗。
    • 若 y>xy>x,A 的棋子进入弃子堆,此后不能再使用。B 的当前棋子留下,A 派出序列中的下一枚棋子继续战斗。
    • 若 x=yx=y,双方当前棋子都进入弃子堆。双方都派出各自序列中的下一枚棋子继续战斗。
  • 若某人需要派出下一枚棋子时已经没有剩余棋子,此人失败,另一人获胜。特别地,如果双方同时需要派出棋子且都已经没有剩余棋子,则本局为平局。

A、B 是好朋友,比起分出胜负,他们更希望得到平局。

给定初始局面以及 mm 次修改。每次修改把其中一个序列的一枚棋子替换成另一个数值,修改的影响会保留到后续修改。在每次修改完成后,判断按此时的两个序列进行对局,是否会得到平局。每次判断均从修改后的完整序列开头重新开始对局,不接续上一次假想对局的战斗状态。

输入格式

第一行包含正整数 n1n_1,1≤n1≤1051\le n_1\le10^5。

第二行包含 n1n_1 个正整数 a1,…,an1a_1,\ldots,a_{n_1},1≤ai≤1051\le a_i\le10^5,表示 A 的序列。

第三行包含正整数 n2n_2,1≤n2≤1051\le n_2\le10^5。

第四行包含 n2n_2 个正整数 b1,…,bn2b_1,\ldots,b_{n_2},1≤bi≤1051\le b_i\le10^5,表示 B 的序列。

第五行包含正整数 mm,1≤m≤2×1051\le m\le2\times10^5。

接下来 mm 行,每行包含三个正整数 o,x,yo,x,y,1≤o≤21\le o\le2,1≤x≤no1\le x\le n_o,1≤y≤1051\le y\le10^5:

  • 若 o=1o=1,将 axa_x 修改为 yy。
  • 若 o=2o=2,将 bxb_x 修改为 yy。

输入只有一组数据。

输出格式

对每次修改输出一行。若修改后的局面会得到平局,输出 YES;否则输出 NO。不需要在任何修改之前输出初始局面的答案。

样例

输入:

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

样例说明

根据原规则独立重演:第四次修改后,双方序列均为 [5,4,3,2,1][5,4,3,2,1],每一轮都相互消耗一对相等棋子,最终同时用尽,所以为平局。

第八次修改后,A=[5,4,3,2,5]A=[5,4,3,2,5],B=[4,4,5,2,5]B=[4,4,5,2,5]。A 的第一枚 55 先后击败 B 的两个 44,再与 B 的第一枚 55 相互消耗。随后 A 的 44 击败 B 的 22;B 的末尾 55 依次击败 A 的 4,3,24,3,2,最后与 A 的末尾 55 相互消耗,双方同时用尽,仍为平局。完整八次原输出保持原样。