#P18865. [HONI 2013/2014 #1] SLASTIČAR

[HONI 2013/2014 #1] SLASTIČAR

题目描述

有一个长度为 NN 的数字串 AA,以及 MM 个要检查的数字串。对每个待查串 BB,机器人从 AA 的第 11 个位置开始尝试匹配。设 BB 长为 LL。

在尝试起点 ii 时,机器人从左到右逐字符比较 AA 的第 ii 至 i+L−1i+L-1 个位置与 BB。超出 AA 末尾的位置视为字符 #。比较遇到第一个不同的字符时,结束这次尝试,并把起点加 11。如果全部 LL 个字符相同,则立即停止这次查询。如果试过全部 NN 个起点都没有匹配,也停止查询。

每比较一对字符收费一克罗地亚库纳,包括发现不相同的那一次。对每个 BB,求查询费用。

输入格式

第一行是 NN,满足 1≤N≤1000001\le N\le 100000。第二行是长度为 NN 的数字串 AA。

第三行是 MM,满足 1≤M≤500001\le M\le50000。接下来 MM 行各给一个非空数字串,长度不超过 100000100000。所有待查串长度之和不超过 30000003000000。

输出格式

输出 MM 行,第 ii 行是查询第 ii 个串的费用。

部分分

20%20\% 的分值满足 N≤1000N\le1000、M≤500M\le500,且每个待查串长不超过 10001000。

样例

样例 1

输入

7
1090901
4
87650
0901
109
090

输出

7
10
3
4

样例 2

输入

10
5821052680
4
210526
2105
582
105268

输出

8
6
3
9

样例 3

输入

3
001
1
11

输出

4