Витрина магазина букв — это строка \(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\).
Обратите внимание, что ответы для друзей надо находить независимо (друзья только лишь оценивают ситуации, но не покупают буквы).
Выходные данные
Для каждого друга выведите длину кратчайшего префикса \(s\), которую ей/ему придётся купить, чтобы написать свое имя. Своё имя можно написать, если в наличии есть все буквы имени (в количестве равном или большем необходимого).
Гарантируется, что каждый друг может написать свое имя, используя буквы из строки \(s\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9
arrayhead
5
arya
harry
ray
r
areahydra
|
5
6
5
2
9
|