阿轩在纸上写了两个字符串，分别记为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

来源

• 《算法竞赛进阶指南》
• acwing 可能含有视频讲解