시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 1 | 1 | 1 | 100.000% |
A ternary string is a sequence of digits, where each digit is either $0$, $1$, or $2$.
For a ternary string, Chiaki can perform any of the following operations:
Chiaki has a ternary string $s$ of length $n$ and $m$ other ternary strings $t_1,t_2,\dots,t_m$. For each ternary string $t_i$, she would like to know the number of pairs $(l, r)$ ($1 \le l \le r \le n$) such that the substring $s_{l..r}$ can become $t_i$ after performing several above operations.
There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$) -- the length of $s$ and the number of other ternary strings.
The second line contains a ternary string $s$ of length $n$.
Each of the next $m$ lines contains a ternary string $t_i$ ($1 \le |t_i| \le 10^6$).
It is guaranteed that the sum of the length of all strings over all test cases does not exceed $2 \times 10^6$.
For each test cases, output $m$ lines, where the $i$-th line contains an integer denoting the answer for ternary string $t_i$.
2 11 4 01021001020 0 1 2 012 6 3 012210 0 1 2
6 3 4 0 2 4 4