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.

제한

힌트