ml2 | Best Ice Cream Flavours

Filippo loves ice cream, so when he found out that a new ice cream shop had opened in Bologna, he had to go and taste their ice cream!

The shop sells $N$ flavours of ice cream, each flavour is represented by a string $F_i$. The ice cream shop offers a special promotion, each customer can choose a non-empty string $s$ and he will receive a cup containing all flavours starting with $s$, for example if the flavours are “chocolate”, “coffee” and “cookies”, by choosing the string “co” you would receive the flavours “coffee” and “cookies” but not the “chocolate” flavour.

Filippo wants to buy exactly $k$ flavours using the fewest number of cups, however Filippo can’t decide which flavours to choose so, to avoid blocking the queue, he decided to buy exactly the first $k$ flavours (i.e. flavours $F_0$, $F_1$, $\dots$, $F_{k−1}$).

Help Filippo find the minimum number of cups needed to buy exactly the first $k$ flavours, for each $k = 1, \dots, N$

Input data

The first line contains the only integer $N$. The next $N$ lines contain a string representing a flavour.

Output data

You need to write $N$ lines with an integer each: the minimum number of cups needed to order all flavours from $0$ to $k − 1$ but none of the flavours from $k$ to $N − 1$, for each $k = 1, \dots, N$.

Constraints and clarifications

• $2 \leq N \leq 100 \ 000$;
• Each flavour is formed by lowercase English characters (a to z).
• The total length of all flavours is at most $2 \ 000 \ 000$.
• All flavours are different.
• It’s guaranteed that it is always possible to buy the first $k$ flavours for each $k$ = $1$, $\dots$, $N$.
• The same flavour is allowed to appear in more than one cup (while still counting as a single flavour).

Example 1

stdin

5
chocolate
coffee
cookies
pistachio
strawberry

stdout

1
2
1
2
3

Explanation

• $k = 1$: Filippo can buy one cup with $s_1$ = “choco”.

• $k = 2$: Filippo can buy two cups with $s_1$ = “choco” and $s_2$ = “coffee”

• $k = 3$: Filippo can buy one cup with $s_1$ = “c”

• $k = 4$: Filippo can buy two cups with $s_1$ = “c” and $s_2$ = “pi”.

• $k = 5$: Filippo can buy three cups with $s_1$ = “c”, $s_2$ = “pi” and $s_3$ = “straw”.

Example 2

stdin

10
orange
peanutbutter
mango
mint
cheesecacke
coconut
oreo
cherry
peppermint
watermelon

stdout

1
2
3
3
4
5
5
4
4
5