Misha has an old Nokia and many friends, so many that it takes a lot of
time to find a phone number.
The friends' names in the phonebook are ordered alphabetically. Passing
from a phone number to the next number on the list is done by pressing the
`down' button, and passing to the preceding number is done by pressing the
`up' button. The list is cyclic, which means that pressing the `up' button
at the first name in the list takes Misha to the last name and pressing
the `down' button at the last name takes him to the first name.
When Misha opens the phonebook, he can see the names of all his friends,
and the current name is the alphabetically first name. If he starts typing
some word on the phone's keyboard, the phone will show only the names
starting with the typed sequence of letters. In this case, the current
name will be the name that alphabetically precedes the other names. If the
last of the typed letters is deleted, then all the names starting with the
shorter sequence of letters become available but the current name remains
the same. If all the letters are deleted, then the current name remains
the same and all the entries in the phonebook become available. If the
sequence that should appear after pressing a button is not a beginning of
any name in the phonebook, the phone will produce an unpleasant sound and
the typed letter will not appear on the screen.
Pressing one button takes exactly one second. The first letter on a button
is typed in one pressing, the second letter is typed in two pressings, and
so on. The keyboard looks as follows:
| abc | def
|
ghi | jkl | mno
|
pqrs | tuv | wxyz
|
You are given a list of Misha's friends. For each name calculate the time
in which Misha can choose this name in the list.
Input
The first line contains the number n of entries in Misha's phonebook (1
≤ n ≤ 105). In each of the following n lines you are given a
nonempty word consisting of lowercase English letters. The words are
ordered alphabetically. All the entries in the phonebook are different.
The total length of the words does not exceed 105.
Output
Output n integers separated with a space. The ith integer must be the
minimum time in which the ith name can be chosen.
Sample
input | output |
---|
5
a
aaa
aab
b
d
| 0 1 2 2 1
|
Problem Author: Mikhail Rubinchik
Problem Source: Ural Regional School Programming Contest 2011