B. Магазин букв
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Витрина магазина букв — это строка $$$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$$$) — количество друзей.

В $$$i$$$-й из следующих $$$m$$$ строк записано $$$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$$$.

Пример
Входные данные
9
arrayhead
5
arya
harry
ray
r
areahydra
Выходные данные
5
6
5
2
9