← 返回题目列表

Codeforces · 1187/B

B. 信件店

中文机器翻译题面 查看原题

商店展示字母是一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。顾名思义,商店里出售信件。

信件是从最左边到最右边一封一封地出售的。任何客户只能购买字符串 $$$s$$$ 中的某些字母前缀。

有$$$m$$$个朋友,其中第$$$i$$$的名字是$$$t_i$$$。他们每个人都计划估计以下值:如果他/她想构建她/他购买的字母的名字,她/他需要购买多少个字母(最短前缀的长度)。如果每个字母以相同或更多的数量出现,则可以构造该名称。

- 例如,对于 $$$s$$$="arrayhead" 和 $$$t_i$$$="arya" 必须购买 $$$5$$$ 字母(“arrayhead”)。
- 例如,对于 $$$s$$$="arrayhead" 和 $$$t_i$$$="harry" 必须购买 $$$6$$$ 字母(“arrayhead”)。
- 例如,对于 $$$s$$$="arrayhead" 和 $$$t_i$$$="ray" 必须购买 $$$5$$$ 字母(“arrayhead”)。
- 例如,对于 $$$s$$$="arrayhead" 和 $$$t_i$$$="r" $$$2$$$ 必须购买字母(“arrayhead”)。
- 例如,对于 $$$s$$$="arrayhead" 和 $$$t_i$$$="areaHydra" 必须购买所有 $$$9$$$ 字母(“arrayhead”)。

保证每个朋友都可以使用字符串$$$s$$$中的字母来构造她/他的名字。

请注意,朋友的价值是独立的,朋友只是估计它们,而不是实际购买信件。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 展示字符串 $$$s$$$ 的长度。

第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — 好友数量。

接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含 $$$t_i$$$ ($$$1 \le |t_i| \le 2 \cdot 10^5$$$) — 第 $$$i$$$ 位好友的姓名。

保证 $$$\sum \limits_{i=1}^m |t_i| \le 2 \cdot 10^5$$$。

输出

为每个朋友打印来自 $$$s$$$ 的字母的最短前缀的长度,他/她需要购买才能构建她/他的名字。如果每个字母以相同或更多的数量出现,则可以构造该名称。

保证每个朋友都可以使用字符串$$$s$$$中的字母来构造她/他的名字。

示例

输入 #1

9
arrayhead
5
arya
harry
ray
r
areahydra

输出 #1

5
6
5
2
9