组织信息学竞赛对 Mirko 来说并没有带来太多利润，因此他开了一家冰淇淋和糕点店。他的生意一直很红火，直到有一天，欧盟卫生检查员决定对他进行访问。

一项新的指令规定了 $M$ 种禁用成分，这些成分即使在极微量的情况下也不能出现在食品中。每种成分都有一个由数字 0 到 9 组成的序列号。每个食品包装上的声明都列出了该食品中所含成分的所有序列号。

Mirko 必须检查他的任何产品是否在其声明中列出了禁用的成分序列号。然而，一如既往地笨拙和粗心的 Mirko 决定将所有序列号拼接成一个长度为 $N$ 的长数字，并相信这会使他的工作更轻松。他从朋友 Slavko 那里借了一个机器人。该机器人被编程为检查序列号 $A$ 是否包含另一个序列号 $B$ 作为子串。让我们用 $L$ 表示 $B$ 的长度。机器人按如下方式进行搜索：

• 首先，它将 $A$ 中从位置 1 到位置 $L$ 的片段与 $B$ 中的数字逐位进行比较。当发现不同的数字或确定片段相等时，停止比较。如果片段相等，则停止搜索并报告匹配。
• 如果片段不相等，则对从位置 2 到 $L+1$ 的片段重复上述过程。如果这些片段也不相等，则继续对片段 3 到 $L+2$、4 到 $L+3$ 等进行搜索。
• 如果机器人没有足够的数字来获取长度为 $L$ 的完整片段（例如，在长度为 8 的序列号中从第 5 个字符开始，需要一个长度为 6 的片段），它将用 '#' 字符填充该片段。例如，"563232" 从位置 4 到位置 10 的片段是 "232####"。
• 如果机器人到达了序列号的末尾（已经尝试了所有 $N$ 个片段）而没有找到 $B$，则报告未找到匹配。

机器人每比较两个数字需要一秒钟，而 Slavko 按每秒一美元向 Mirko 收取使用机器人的费用。

请帮助 Mirko 确定他需要支付给 Slavko 多少钱来进行模式匹配！

输入格式

输入的第一行包含一个正整数 $N$（$1 \le N \le 100\,000$），表示长序列号的长度。

第二行包含 $N$ 个 0 到 9 之间的数字，表示该长序列号。

第三行包含一个正整数 $M$（$1 \le M \le 50\,000$），表示禁用成分的数量。

接下来的 $M$ 行，每行包含一个禁用成分的序列号。

单个禁用成分序列号的长度不会超过 $100\,000$。

所有禁用成分序列号的总长度不会超过 $3\,000\,000$。

输出格式

输出 $M$ 个整数，每行一个。第 $i$ 行必须包含 Mirko 为搜索第 $i$ 个成分序列号而需要支付给 Slavko 的美元金额。

子任务

在占总分至少 20% 的测试数据中，满足以下限制条件：

• $1 \le N \le 1000$
• $1 \le M \le 500$
• 单个禁用成分序列号的长度不超过 1000

样例

输入样例 1

7
1090901
4
87650
0901
109
090

输出样例 1

7
10
3
4

输入样例 2

10
5821052680
4
210526
2105
582
105268

输出样例 2

8
6
3
9

输入样例 3

3
001
1
11

输出样例 3

4

说明

第一个样例的解释：

• 第一个序列号：机器人在每个片段中都发现第一个数字不同——总共进行了 7 次比较。
• 第二个序列号：尝试第一个位置，立即发现不同（1 次比较）。尝试第二个位置，在第四个数字处发现不同（4 次比较）。尝试第三个位置，立即发现不同（1 次比较）。尝试第四个位置，找到匹配（4 次比较）。总计：10 次比较。
• 第三个序列号：立即找到匹配（3 次比较）。
• 第四个序列号：在第二个位置找到匹配（$1 + 3 = 4$ 次比较）。

第三个样例的解释：

机器人依次将序列号 '11' 与片段 '00'（1 次比较）、'01'（1 次比较）和 '1#'（2 次比较）进行比较。总计：4 次比较。