B. Тындекс.Бром
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

И снова Тындекс догоняет и перегоняет своих конкурентов! В ответ на выход Жужль Хром явился новый браузер — Тындекс.Бром!

С каждым днём растёт популярность нового браузера. И дело даже не в том, что в него встроен Тындекс.Бар, который, после покупки Тындекс.Бутылки и подключения её к USB-порту, автоматически наполняет тару прекрасным коньяком 1664 года; а благодаря продуманному взаимодействию с пользователем.

Возьмём, например, систему автоматического исправления адреса. Вы ввели codehorses вместо codeforces? Унылый Жужль Хром уныло скажет, мол, нет такого адреса. В то же время Тындекс.Бром автоматически подберёт ближайший адрес и отправит вас именно туда. Гениально!

Как же работает эта замечательная система? Очень просто! Для каждого потенциального адреса вычисляется функция ошибки F по следующим правилам:

  • для каждой буквы ci из потенциального адреса c находится ближайшая позиция j этой же буквы во введенном пользователем адресе s. К F прибавляется модуль разности этих позиций |i - j|. То есть для каждого i (1 ≤ i ≤ |c|) позиция j выбирается таким образом, что ci = sj, а |i - j| минимально.
  • если такой буквы ci во введенном пользователем адресе нет, то к F прибавляется длина потенциального адреса |c|

После вычисления значений функции ошибки для всех потенциальных адресов выбирается наиболее подходящий.

Для того чтобы лучше разобраться в особенностях описанного выше способа, рекомендуется реализовать алгоритм вычисления функции F для заданного пользователем адреса и некоторого набора потенциальных адресов. Дерзайте!

Входные данные

В первой строке дано два целых числа n и k (1 ≤ n ≤ 105, 1 ≤ k ≤ 105) — количество потенциальных адресов и длина введённого пользователем адреса. В следующей строке записано k строчных латинских букв — введённый пользователем адрес s. В каждой последующей i-ой (1 ≤ i ≤ n) строке дана непустая последовательность из строчных латинских букв — собственно потенциальный адрес. Гарантируется, что суммарная длина всех строк не превышает 2·105.

Выходные данные

В каждой из n строк выходного файла выведите одно число: значение функции ошибки при выборе текущего потенциального адреса.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).

Примеры
Входные данные
2 10
codeforces
codeforces
codehorses
Выходные данные
0
12
Входные данные
9 9
vkontakte
vcontacte
vkontrakte
vkollapse
vkrokodile
vtopke
vkapuste
vpechke
vk
vcodeforcese
Выходные данные
18
14
36
47
14
29
30
0
84