seuOJ540 - YiYi Loves Beautiful Number String

题目描述

称一个仅由数字构成的长度大于等于 22 的字符串 ss 是美丽的当且仅当存在一个下标 kk，使得 ∑i=1ksi=number(sk+1sk+2…sn)\sum_{i=1}^k s_i=number(s_{k+1}s_{k+2}\dots s_n)。

对于一个仅由数字构成的字符串 tt 来说，number(t)number(t) 等于将 tt 转成一个整数后的值。例如 number("123")=123number("123")=123，number("0109")=109number("0109")=109。

字符串 "235""235" 是一个美丽的字符串，因为 2+3=number("5")=52+3=number("5")=5；字符串 333413333413 也是一个美丽的字符串，选择 k=4k=4，那么 3+3+3+4=number("13")=133+3+3+4=number("13")=13。

YiYi 现在有一个长度为 n(n≥2)n(n\ge2) 的仅由数字构成的字符串 ss，在每次操作中，她会选择一个下标 i(1≤i≤n)i(1\le i\le n)，使得 si=c(0≤c≤9)s_i=c(0\le c\le 9)。在她每一次操作结束后，请你回答，假如可以对字符串 ss 进行任意重新排列，能否使得字符串 ss 成为一个美丽的字符串。

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t\le 10^4)，代表数据组数。

对于每组数据：

第一行，两个整数 n,q(2≤n≤5⋅105;1≤q≤5⋅105)n,q(2\le n \le 5\cdot10^5;1\le q\le 5\cdot 10^5)，代表 YiYi 的数字字符串的长度和操作次数。

第二行，一个长的为 nn 仅有数字构成的字符串 ss，代表初始时的字符串。

接下来连续的 qq 行，每行两个整数 pos,c(1≤pos≤n;0≤c≤9)pos,c(1\le pos \le n;0\le c\le 9)，代表这一次操作将 sposs_{pos} 修改为 cc。

保证同一测试点内 nn 和 qq 的总和均不超过 5⋅1055\cdot 10^5。

输出格式

在每一次修改结束后，在可以对字符串 ss 进行任意重新排列的情况下，如果能够使得字符串 ss 是美丽的，输出 "YES";否则，输出 "NO"。

样例

输入样例

4
4 2
0909
3 9
2 0
3 3
520
3 3
1 1
3 1
2 1
09
1 9
8 5
01230123
3 4
6 6
1 5
2 2
8 3

输出样例

NO
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO