While rummaging through things in a distant drawer, Anya found a beautiful string s…
- User
While rummaging through things in a distant drawer, Anya found a beautiful string s consisting only of zeros and ones.
Now she wants to make it even more beautiful by performing q operations on it.
Each operation is described by two integers i (1≤i≤|s| ) and v (v∈{0,1} ) and means that the i -th character of the string is assigned the value v (that is, the assignment si=v is performed).
But Anya loves the number 1100 , so after each query, she asks you to tell her whether the substring "1100" is present in her string (i.e. there exist such 1≤i≤|s|−3 that sisi+1si+2si+3=1100 ).
Input The first line contains one integer t (1≤t≤104 ) — the number of test cases.
The first line of the test case contains the string s (1≤|s|≤2⋅105 ), consisting only of the characters "0" and "1". Here |s| denotes the length of the string s .
The next line contains an integer q (1≤q≤2⋅105 ) — the number of queries.
The following q lines contain two integers i (1≤i≤|s| ) and v (v∈{0,1} ), describing the query.
It is guaranteed that the sum of |s| across all test cases does not exceed 2⋅105 . It is also guaranteed that the sum of q across all test cases does not exceed 2⋅105 .
Output For each query, output "YES", if "1100" is present in Anya's string; otherwise, output "NO".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
Example InputCopy 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 OutputCopy NO NO NO NO YES YES NO NO YES YES YES NO NO NO NO
- Assistant
To determine whether the substring "1100" exists in the binary string after each operation, we approach each test case individually. Here's a step-by-step analysis for the given input:
Test Case 1:
- Initial string:
"100" - Operations:
- Set position 1 to
1: The string becomes"100". No "1100" substring. - Set position 2 to
0: The string remains"100". No "1100" substring. - Set position 2 to
0: The string remains"100". No "1100" substring. - Set position 3 to
1: The string becomes"101". No "1100" substring.
- Set position 1 to
- Output:
NO,NO,NO,NO
Test Case 2:
- Initial string:
"1100000" - Operations:
- Set position 6 to
1: The string becomes"1100010". It contains "1100". - Set position 7 to
1: The string becomes"1100011". It still contains "1100". - Set position 4 to
1: The string becomes"1101011". Now, "1100" is no longer present.
- Set position 6 to
- Output:
YES,YES,NO
Test Case 3:
- Initial string:
"111010" - Operations:
- Set position 1 to
1: The string remains"111010". No change, no "1100". - Set position 5 to
0: The string becomes"111000". It contains "1100". - Set position 4 to
1: The string becomes"111100". It contains "1100". - Set position 5 to
0: The string becomes"111100". It still contains "1100".
- Set position 1 to
- Output:
YES,YES,YES,NO
Test Case 4:
- Initial string:
"0100" - Operations:
- Set position 3 to
1: The string becomes"0110". No "1100" substring. - Set position 1 to
1: The string becomes"1110". No "1100" substring. - Set position 2 to
0: The string becomes"1010". No "1100" substring. - Set position 2 to
1: The string becomes"1110". Still no "1100" substring.
- Set position 3 to
- Output:
NO,NO,NO,NO
Final Output:
NO NO NO NO YES YES NO NO YES YES YES NO NO NO NO - Initial string: