题目描述

阿轩在纸上写了两个字符串，分别记为$\red{A}$和$\red{B}$。

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

不过阿轩是一个勤学好问的同学，他向你提出了$\red{Q}$个问题：

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

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

因此$\red{A}$有$\red{4}$个位置与$\red{B}$的匹配长度恰好为$\red{0}$，有$\red{1}$个位置的匹配长度恰好为$\red{1}$，有$\red{1}$个位置的匹配长度恰好为$\red{2}$。

输入格式

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

第二行输入字符串$\red{A}$，第三行输入字符串$\red{B}$。

接下来$\red{Q}$行每行输入$\red{1}$个整数$\red{x}$，表示一个问题。

输出格式

输出共$\red{Q}$行，依次表示每个问题的答案。

样例

输入样例

6 2 5
aabcde
ab
0
1
2
3
4

输出样例

4
1
1
0
0

提示

$\red{1≤N,M,Q,x≤200000}$