시간 제한메모리 제한제출정답맞힌 사람정답 비율
12 초 (추가 시간 없음) 512 MB111100.000%

문제

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.

예제 입력 1

9 2 10
123456789
9 12
8 123456789

예제 출력 1

24
45

예제 입력 2

5 10 5
01234
0 1
1 1
2 1
3 1
4 1
0 1
1 0
2 0
3 0
4 0

예제 출력 2

1
13
9
9
9
1
10
9
10
6