#T5. 优美字符串

优美字符串

题目描述

有一天,你发现了一个只由 00 和 11 组成的优美字符串 ss 。

现在,你想对它进行 qq 运算,让它变得更加优美。

每个操作由两个整数 ii ( 1≤i≤∣s∣1 \le i \le |s| ) 和 vv ( v∈{0,1}v \in \{0, 1\} )来描述,这意味着字符串中的第 ii 个字符被赋值为 vv (即执行赋值 si=vs_i = v )。

但你喜欢数字 11001100 ,所以每次查询后,你都想知道这个优美字符串中是否存在子串 1100(即存在 1≤i≤∣s∣−31 \le i \le |s| - 3 和 sisi+1si+2si+3=1100s_{i}s_{i + 1}s_{i + 2}s_{i + 3} = \texttt{1100} 这样的字符串)。

输入格式

第一行包含一个整数 tt ( 1≤t≤1041 \leq t \leq 10^4 ) - 测试用例数。

测试用例的第一行包含字符串 ss ( 1≤∣s∣≤2⋅1051 \leq |s| \leq 2 \cdot 10^5 ),仅由字符 0 和 1 组成。这里的 ∣s∣|s| 表示字符串 ss 的长度。

下一行包含一个整数 qq ( 1≤q≤2⋅1051 \leq q \leq 2 \cdot 10^5 ) - 查询次数。

接下来的 qq 行包含两个整数 ii ( 1≤i≤∣s∣1 \leq i \leq |s| ) 和 vv ( v∈{0,1}v \in \{0, 1\} ),用于描述查询。

保证所有测试用例中 ∣s∣|s| 的总和不超过 2⋅1052 \cdot 10^5 。同时保证所有测试用例中 qq 的总和不超过 2⋅1052 \cdot 10^5 。

输出格式

对于每个查询,如果安雅的字符串中有 1100,则输出 YES;否则,输出 NO。

样例 #1

样例输入 #1

4
100
4
1 1
2 0
2 0
3 1
1100000
3
6 1
7 1
4 1
111010
4
1 1
5 0
4 1
5 0
0100
4
3 1
1 1
2 0
2 1

样例输出 #1

NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO

子任务数据规模:

对于 20%20 \% 的测试数据,额外满足 1≤∣s∣≤1021 \leq |s| \leq 10^2。

对于 50%50 \% 的测试数据,额外满足 1≤∣s∣≤1041 \leq |s| \leq 10^4。