У Миши есть старенькая Nokia и много друзей. Так много, что Мише постоянно приходится тратить кучу времени на поиск нужного номера.
Имена друзей в телефонном справочнике упорядочены по алфавиту. От текущего имени в списке можно перейти к следующему с помощью кнопки «вниз»,
а к предыдущему — с помощью кнопки «вверх». Кроме того, список зациклен, то есть нажатие кнопки «вверх» для самого первого имени
в справочнике переводит на последнее имя в нём, а нажатие кнопки «вниз» для последнего имени переводит на первое имя.
Когда Миша открывает справочник, в нём видны имена всех друзей, а текущим является первое по алфавиту имя.
Если начать набирать некоторое слово на клавиатуре телефона, то в справочнике будут отображаться
только имена, начинающиеся на уже введённую последовательность букв. Текущим в этом случае также станет имя, идущее раньше
остальных в алфавитном порядке. Если после этого стереть последнюю введённую букву, позиция в справочнике не изменится,
а доступными станут все имена, начинающиеся на более короткую строку. Если стереть все буквы, то доступными станут все записи в справочнике, а текущее имя не изменится. Если после некоторого нажатия должна появиться последовательность букв, на которую не начинается ни одно имя,
то телефон издаст неприятный звук и последняя введённая буква не появится на экране.
На одно нажатие кнопки у Миши уходит ровно одна секунда. Первая буква на кнопке набирается за одно нажатие, вторая за два и т.д.
Клавиатура телефона выглядит так:
| abc | def
|
ghi | jkl | mno
|
pqrs | tuv | wxyz
|
Дан список имён друзей Миши. Для каждого имени вычислите минимальное время, за которое Миша сможет выбрать это имя в списке.
Исходные данные
В первой строке дано целое число n — количество записей в телефонном справочнике Миши (1 ≤ n ≤ 105). Далее в n строках записано по одному непустому
слову из строчных латинских букв. Слова перечислены в алфавитном порядке. Все записи в справочнике различны. Суммарная длина всех слов не превосходит 105.
Результат
Выведите n чисел через пробел. i-е число должно равняться минимальному
времени нахождения i-го имени в справочнике.
Пример
исходные данные | результат |
---|
5
a
aaa
aab
b
d
| 0 1 2 2 1
|
Автор задачи: Михаил Рубинчик
Источник задачи: Уральская региональная командная олимпиада по программированию 2011