题目背景

你需要比较一些序列号。

题目描述

现有 $M$ 个由数字 $0$ 到 $9$ 组成的短序列号和一个长度为 $N$ 的长序列号。

检查序列号 $A$ 是否包含长度为 $L$ 的序列号 $B$ 的过程如下：

• 将 $A$ 从位置 $1$ 到 $L$ 逐位与 $B$ 比较，一找到不同就将搜索段整体向后移，如果确定相等则停止比较。

• 将搜索段后移意为把 $x$ 到 $y$ 的搜索区域后移为 $x+1$ 和 $y+1$。

• 若剩下用于比较的位数不够，则在字符串末尾填充 #。如字符串为 563232，从位置 $4$ 到 $10$ 的填充为 232####。

• 若尝试了所有段均不匹配则停止比较。

对于每个短序列号，输出停止比较前比较的次数。

输入格式

输入的第一行是正整数 $N$。

输入的第二行是一个长度为 $N$ 的长序列号。

输入的第三行包含正整数 $M$。

接下来 $M$ 行每行包含一个长度不超过 $10^5$ 的短序列号。

短序列号总长度不超过 $3\times 10^6$。

输出格式

输出 $M$ 个整数，即对于第 $i$ 个短序列号所需的比较次数。

7
1090901
4
87650
0901
109
090 

7
10
3
4

10
5821052680
4
210526
2105
582
105268

8
6
3
9

3
001
1
11

4

提示

【数据规模与约定】

• 对于 $20\%$ 的数据，$1\le N\le 10^3$，$1\le M\le 500$，任意短序列号长度均不超过 $10^3$。
• 对于 $100\%$ 的数据，满足 $1\le N\le 10^5$，$1\le M\le 5\times 10^4$。
• 对于任意序列号中的一位字符 $c$，满足 $c\in\{0,1,2,3,4,5,6,7,8,9 \}$。

【样例解释】

样例 1 解释

第一个序列号：

• 机器人为每个段查找不同的第一位数字，总共进行 $7$ 次比较。

第二个序列号：

• 尝试第一个位置，立即发现差异，$1$ 次比较。
• 尝试第二个位置，找到第四个数字的差异，$4$ 次比较。
• 尝试第三个位置，立即找到差异，$1$ 次比较。
• 尝试第四个位置，找到匹配，$4$个比较。
• 总计 $10$ 次比较。

第三序列号：

• 立即找到匹配项，总计 $3$ 个比较。

第四个序列号：

• 在第二个位置找到匹配项，总计 $1+3=4$ 个比较。

样例 3 解释

按顺序将序列号 11 与段 00，$1$ 次比较，01，$1$ 次比较，和1#，$2$ 次比较，总计 $4$ 次比较。

---

【说明】

题目译自 COCI2013-2014 CONTEST #1 T6 SLASTIČAR。