Forgiveness

Little Q is now checking whether string $A$ matches $B$. Two strings are considered matched if they have the same length, and there are no position $i$ that $A_i$ is different from $B_i$.
However, Little Q is a kind man, he forgives every person hurt him. What's more, he even forgives strings! He gives the string 3 opportunities, if there are no more than 3 positions $i$ that $A_i$ is different from $B_i$, then Little Q will also consider the two strings matched.
For a string $S$, $S[l,r]$ means the substring combined by $S_l, S_{l+1}, ..., S_r$. And the function $occ(A,B)$ returns the number of substrings in string $B$ which matches $A$.
Little Q now has a long numeric 1-based string $S$, and his job is to deal with $m$ operations:

1. + $l$ $r$ $k$, for every positions from $l$ to $r$, change $S_i$ to $(S_i+k)\bmod 10$.
2. ? $l$ $r$ $T$, report $occ(T,S[l,r])$.

After lots of work, Little Q is very tired now, please write a program to help him deal with these operations.

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.
In each test case, there are two integers $n(1\leq n\leq 50000)$ and $m(1\leq m\leq 50000)$ in the first line, denoting the length of string $S$ and the number of operations.
The second line of the input contains a numeric string $S$ with $n$ integers, each number $S_i$ is in the range of 0 to 9.
In the following $m$ lines, each line describes an operation.
If it is a modification, then it is in the format of ''+ $l$ $r$ $k$'', where $1\leq l\leq r\leq n$ and $1\leq k\leq 9$.
If it is a query, then it is in the format of ''? $l$ $r$ $T$'', where $1\leq l\leq r\leq n$ and $T$ is a numeric string composed of integers from 0 to 9.
It is guaranteed that $\sum|T|\leq 100000$ in each test case, and there are no more than $4$ test cases satisfying $\min(n,m)>1000$.

For each query, print a single line with an integer, denoting the answer.

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

1
1
0
1