UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4924. [Lydsy1706月赛]原谅字符串

统计 下载数据

Description

小Q正在检查字符串A是否匹配B。两个串被认为是匹配的,当且仅当它们长度相等,并且不存在一个位置i,满足A_i不等于B_i。
但是,小Q戴了原谅帽,他甚至可以原谅字符串!他给了字符串3次机会,如果有不超过3个这样不同的位置i,那么他也会认为两个串匹配。
对于一个字符串S,S[l,r]表示S的[l,r]区间组成的子串。函数occ(A,B)返回A与B中多少个连续子串匹配。
小Q现在有一个下标从1开始的数字串S,他的工作是处理m个操作:
+ l r k,对于l到r的每个位置i,将S_i修改为(S_i+k) mod 10。
? l r T,查询occ(T,S[l,r])。
在大量重复的工作之后,小Q感到非常疲惫。请写一个程序,帮助小Q处理这些操作。

Input

第一行包含一个正整数T(1<=T<=15),表示测试数据的组数。
每组测试数据中,第一行包含两个正整数n(1<=n<=50000)和m(1<=m<=50000),分别表示字符串S的长度以及操作的个数。
第二行为一个长度为n的十进制数字串S。
接下来m行,每行描述一个操作:
如果是一个修改,那么格式为+ l r k,其中1<=l<=r<=n且1<=k<=9。
如果是一个询问,那么格式为? l r T,其中1<=l<=r<=n,且T也是一个十进制数字串。
输入数据保证每组数据中sum(|T|)<=100000,且不超过4组数据满足min(n,m)>1000。

Output

对于每个询问,输出一行一个整数,即答案。

Sample Input

1
5 5
01234
? 2 5 1234
? 2 5 1777
? 2 5 9999
+ 1 5 5
? 1 5 56789

Sample Output

1
1
0
1

Hint

Source

claris原创,本oj版权所有,翻版必究