23489번 - Digital Root 다국어

Chiaki has a $B$-based digital string $s$ of length $n$. She has prepared $m$ queries for  the string. 

In the $i$-th query, she would like to know the number of substring $s_{l..r}$ ($1 \le l \le r \le n$) of $s$ such that after changing at most one digit in $s_{l..r}$ to some digit in the set $A_i$, the digital root of $s_{l..r}$ equals to $x_i$.

We should remind you that a digital root $d(x)$ of the $B$-based digital string $x$ ($x$ may have some leading zeros) is the sum $s(x)$ of all the digits of this number, if $s(x) \le B - 1$, otherwise it is $d(s(x))$. For example, a digital root of the number $6543_{10}$ is calculated as follows: $d(6543_{10}) = d(6_{10} + 5_{10} + 4_{10} + 3_{10}) = d(18_{10}) = 9_{10}$, $d(abcd_{16})=d(2e_{16})=d(10_{16})=1_{16}$.

Note that in this problem we will use the lowercase English letters from 'a' to 'f' to represent the digits with values from $10$ to $15$.

The first line contains three integers $n$, $m$ and $B$ ($1 \le n, m \le 2^{20}, 2 \le B \le 16$) -- the length of the string, the number of queries and the base of the number.

The second line contains a $B$-based digital string $s$ of length $n$.

Each of the following $m$ lines contains a character $x_i$ and a $B$-based string $a_i$ ($1 \le |a_i| \le B$)-- the expected value of digital root and the set $A_i$. All characters in $a_i$ are distinct.

For each query, output an integer denoting the number of substrings.