Chiaki 有一个 $B$ 进制的数字字符串 $s$，长度为 $n$。她准备了 $m$ 个关于该字符串的查询。

在第 $i$ 个查询中，她想知道有多少个 $s$ 的子串 $s_{l..r}$ ($1 \le l \le r \le n$)，满足在将 $s_{l..r}$ 中的至多一个数字修改为集合 $A_i$ 中的某个数字后，$s_{l..r}$ 的数字根等于 $x_i$。

我们提醒你，$B$ 进制数字字符串 $x$（$x$ 可能包含前导零）的数字根 $d(x)$ 定义为：若 $x$ 中所有数字之和 $s(x) \le B - 1$，则 $d(x) = s(x)$；否则 $d(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}$。

注意，在本题中，我们使用小写英文字母 'a' 到 'f' 来表示数值从 10 到 15 的数字。

输入格式

第一行包含三个整数 $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$。$a_i$ 中的所有字符各不相同。

输出格式

对于每个查询，输出一个整数，表示满足条件的子串数量。

样例

样例输入 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