Kimariji Key Keeper

問題文

4869高校かるた部では、参加者から集めた文字列を使ってかるた大会を行うことにしました。

かるた大会で絶対に勝ちたいyuki君は、集めた文字列の中でどの文字列が読まれたかをいち早く $1$ つに確定させるべく、各文字列の決まり字の長さを調べておくことにしました。

ここである文字列集合において、要素である各文字列の決まり字の長さは次のように定義されます。

文字列の集合を $T$ 、文字列 $s \in T$ の長さを $|s|$ とする。
また、$s$ の先頭から $k$ 文字を取り出した文字列を、$s$ の長さ $k$ の接頭辞と呼ぶ。

文字列 $s$ の決まり字の長さ $A_s$ は、次の条件を満たす最小の整数 $k$ とする。

• $1 \leq k \leq |s|$
• 集合 $T$ に含まれる文字列のうち、“$s$ の長さ $k$ の接頭辞”を接頭辞にもつ文字列が、$s$ ただ 1 つである。

はじめ、文字列の集合 $T$ は空です。

これから $Q$ 個の文字列 $S_1,S_2,\ldots,S_Q$ が集合 $T$ に順番に追加されます。

$i$ 番目のクエリでは、文字列 $S_i$ を新たに追加し、その時点で集合 $T$ に含まれるすべての文字列の決まり字の長さの総和 $\sum_{s \in T} A_s$ を出力してください。

制約

• $1 \leq Q \leq 3 \times 10^5$
• $2 \leq |S_i| \leq 6 \times 10^5$
• $S_i$ は英小文字および最後の文字を示す 0 からなる文字列である。
• $S_i$ の最後の文字は 0 である。
• $S_i$ の最後の文字を除いた部分は、すべて英小文字である。
• $S_1,S_2,\ldots,S_Q$ は相異なる。
• $\displaystyle \sum_{i=1}^{Q} |S_i| \leq 6 \times 10^5$

入力

入力は以下の形式で標準入力から与えられる。

出力

$Q$ 行出力してください。 $i$ 行目には、クエリ $i$ の答えを出力してください。

入力例１

4
apple0
ape0
banana0
app0

出力例１

1
6
7
12

クエリ $1$ では、集合 $T$に apple0 しか存在しないため、apple0 の決まり字の長さは $1$ です。

クエリ $2$ で ape0 が追加されると、apple0 と ape0 は先頭の ap が一致します。そのため、どちらも決まり字の長さは $3$ です。

このように既に追加されている文字列の決まり字の長さが増減しうることに注意してください。

クエリ $3$ では、集合 $T$ に接頭辞が b の文字列は banana のみです。そのため、 banana の決まり字の長さは $1$ です。また、apple0 と ape0 の決まり字の長さは増減しません。

入力例２

3
cat0
dog0
fish0

出力例２

1
2
3

どの文字列も先頭文字が異なります。

そのため、すべてのクエリにおいて、すべての文字列の決まり字の長さは $1$ です。

入力例３

5
a0
aa0
aaa0
aaaa0
aaaaa0

出力例３

1
4
8
13
19