У вас есть множество строк \(S\). Каждая строка состоит из строчных букв латинского алфавита.
Для каждой строки вы хотите посчитать, сколько секунд потребуется, чтобы набрать ее в вашем текстовом редакторе. Чтобы набрать строку, вам нужно начать с пустой строки и преобразовать ее в ту строку, которую вы хотите набрать, при помощи следующих операций:
- для текущей строки \(t\) можно выбрать любую строчную латинскую букву \(c\) и приписать ее \(t\), после чего текущая строка станет \(t + c\). Это действие требует \(1\) секунду;
- использовать автодополнение. При использовании автодополнения с текущей строкой \(t\) вам показывается список всех таких строк \(s \in S\), что \(t\) — префикс \(s\). Этот список включает саму строку \(t\), если \(t\) принадлежит \(S\), и строки в нем расположены в лексикографическом порядке. Вы можете превратить \(t\) в \(i\)-ю строку из этого списка за \(i\) секунд. Обратите внимание, что вы можете выбирать любую строку из списка, это не обязательно должна быть та строка, которую вы хотите набрать.
Чему равно минимальное количество секунд, которое нужно затратить, чтобы набрать каждую строку из \(S\)?
Обратите внимание, что строки множества \(S\) задаются во входных данных необычным образом.
Выходные данные
Выведите \(k\) целых чисел, \(i\)-е из которых должно быть равно минимальному количеству секунд, требуемому, чтобы набрать строку \(s_{a_i}\).
Примечание
В первом примере \(S\) состоит из следующих строк: ieh, iqgp, i, iqge, ier.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
0 i
1 q
2 g
0 k
1 e
5 r
4 m
5 h
3 p
3 e
5
8 9 1 10 6
|
2 4 1 3 3
|
|
2
|
8
0 a
1 b
2 a
2 b
4 a
4 b
5 c
6 d
5
2 3 4 7 8
|
1 2 2 4 4
|