160. 匹配统计

阿轩在纸上写了两个字符串,分别记为 $A$ 和 $B$。

利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串 $A$ 从任意位置开始的后缀子串”与“字符串 $B$”匹配的长度。

不过阿轩是一个勤学好问的同学,他向你提出了 $Q$ 个问题:

在每个问题中,他给定你一个整数 $x$,请你告诉他有多少个位置,满足“字符串 $A$ 从该位置开始的后缀子串”与 $B$ 匹配的长度恰好为 $x$。

例如:$A=aabcde,B=ab$,则 $A$ 有 $aabcde、abcde、bcde、cde、de、e$ 这 $6$ 个后缀子串,它们与 $B=ab$ 的匹配长度分别是 $1、2、0、0、0、0$。

因此 $A$ 有 $4$ 个位置与 $B$ 的匹配长度恰好为 $0$,有 $1$ 个位置的匹配长度恰好为 $1$,有 $1$ 个位置的匹配长度恰好为 $2$。

输入格式

第一行输入三个整数 $N,M,Q$,分别表示 $A$ 串长度、$B$ 串长度、问题个数。

第二行输入字符串 $A$,第三行输入字符串 $B$。

接下来 $Q$ 行每行输入 $1$ 个整数 $x$,表示一个问题。

输出格式

输出共 $Q$ 行,依次表示每个问题的答案。

数据范围

$1 \le N,M,Q,x \le 200000$

输入样例:

6 2 5
aabcde
ab
0
1
2
3
4

输出样例:

4
1
1
0
0