디지털 루트

시간 제한: 12000 ms. 메모리 제한: 512 MB.

Chiaki에게 길이가 $n$인 $B$진법 숫자열 $s$가 있다. 그녀는 이 문자열에 대한 질의 $m$개를 준비했다.

$i$번째 질의에서는 부분 문자열 $s_{l..r}$ ($1 \le l \le r \le n$) 중에서, $s_{l..r}$의 자릿수를 최대 한 개 골라 $A_i$에 속한 숫자 중 하나로 바꾸었을 때 $s_{l..r}$의 디지털 루트가 $x_i$와 같아지는 부분 문자열의 개수를 구한다.

$B$진법 숫자열 $x$ (앞에 0이 올 수 있다)의 디지털 루트 $d(x)$는, $x$의 모든 자릿수의 합 $s(x)$가 $B-1$ 이하이면 $s(x)$이고, 그렇지 않으면 $d(s(x))$이다. 예를 들어 $6543_{10}$의 디지털 루트는 $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}$이다.

이 문제에서 값이 10부터 15까지인 숫자는 영문 소문자 'a'부터 'f'로 나타낸다.

첫째 줄에 세 정수 $n$, $m$, $B$가 주어진다 ($1 \le n, m \le 2^{20}$, $2 \le B \le 16$).

둘째 줄에는 길이가 $n$인 $B$진법 숫자열 $s$가 주어진다.

이어지는 $m$개의 줄에는 각각 문자 $x_i$와 $B$진법 문자열 $a_i$ ($1 \le |a_i| \le B$)가 주어진다. $a_i$의 모든 문자는 서로 다르다.

각 질의에 대해 부분 문자열의 개수를 한 줄에 하나씩 출력한다.