题目描述

阿轩在纸上写了两个字符串，分别记为 $A$ 和 $B$。利用在数据结构与算法课上学到的知识，他很容易地求出了「字符串 $A$ 从任意位置开始的后缀子串」与字符串 $B$ 匹配的长度。

不过阿轩是一个勤学好问的同学，他向你提出了 $Q$ 个问题：在每个问题中，他给定你一个整数 $X$，请你告诉他有多少个位置，满足「字符串 $A$ 从该位置开始的后缀子串」与 $B$ 匹配的长度恰好为 $X$。

例如：$A=\texttt{aabcde}$，$B=\texttt{ab}$，则 $A$ 有 $\texttt{aabcde}$、$\texttt{abcde}$、$\texttt{bcde}$、$\texttt{cde}$、$\texttt{de}$、$\texttt{e}$ 这 $6$ 个后缀子串，它们与 $B=\texttt{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$ 行，依次表示每个问题的答案。

6 2 5
aabcde
ab
0
1
2
3
4

4
1
1
0
0

提示

数据保证，$1\leq N,M,Q\leq 2 \times 10^5$，$0 \le X \le 2 \times 10^5$。