Ex - snukesnuke Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

高橋君は人 1,\ldots,N の N 人のあだ名を決めることになりました。

人 i はあだ名を S_i にしてほしいと思っています。複数人に同じあだ名をつけるのを避けるため、高橋君は次の手順で N 人のあだ名を決めることにしました。

  • i=1,\ldots,N の順に、以下の操作により人 i のあだ名を決める
    • 変数 k_i を 1 とする。
    • 「S_i を k_i 回繰り返した文字列」がすでに誰かのあだ名である間、k_i を 1 増やすことを繰り返す。
    • 「S_i を k_i 回繰り返した文字列」を人 i のあだ名とする。

N 人のあだ名を決めた後の k_1,\ldots,k_N を求めてください。

制約

  • N \geq 1
  • S_i は英小文字のみからなる、長さ 1 以上の文字列
  • S_i の長さの総和は 2\times 10^5 以下

入力

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

N
S_1
\vdots
S_N

出力

問題文中の操作により N 人のあだ名を決めた後の k_1,\ldots,k_N をこの順に空白区切りで出力せよ。

入力例 1

3
snuke
snuke
rng

出力例 1

1 2 1
  • まず人 1 のあだ名を決めます。
    • k_1=1 とします。
    • S_1 を k_1 回繰り返した文字列 snuke は誰のあだ名でもないので、人 1 のあだ名は snuke になります。
  • 次に人 2 のあだ名を決めます。
    • k_2=1 とします。
    • S_2 を k_2 回繰り返した文字列 snuke はすでに人 1 のあだ名なので、k_2 を 1 増やして 2 とします。
    • S_2 を k_2 回繰り返した文字列 snukesnuke は誰のあだ名でもないので、人 2 のあだ名は snukesnuke になります。
  • 最後に人 3 のあだ名を決めます。
    • k_3=1 とします。
    • S_3 を k_3 回繰り返した文字列 rng は誰のあだ名でもないので、人 3 のあだ名は rng になります。

以上により、k_1,k_2,k_3 はそれぞれ 1,2,1 となります。

入力例 2

4
aa
a
a
aaa

出力例 2

1 1 3 2
  • 人 1 のあだ名は aa になります。
  • 人 2 のあだ名は a になります。
  • 人 3 のあだ名は、a, aa がすでに他の人のあだ名なので、aaa になります。
  • 人 4 のあだ名は、aaa がすでに他の人のあだ名なので、aaaaaa になります。

入力例 3

5
x
x
x
x
x

出力例 3

1 2 3 4 5

Score : 600 points

Problem Statement

Takahashi is going to decide nicknames of N people, person 1,\ldots,N.

Person i wants a nickname S_i. To avoid giving the same nickname to multiple people, he is going to decide their nicknames as follows:

  • For each i=1,\ldots,N in order, decide person i's nickname as follows:
    • Initialize a variable k_i with 1.
    • Repeatedly increment k_i by one while the k_i-time repetition of S_i is someone's nickname.
    • Let person i's nickname be the k_i-time repetition of S_i.

Find k_1,\ldots, and k_N after deciding nicknames of the N people.

Constraints

  • N \geq 1
  • S_i is a string of length at least 1 consisting of lowercase English letters.
  • The sum of lengths of S_i is at most 2\times 10^5.

Input

The input is given from Standard Input in the following format:

N
S_1
\vdots
S_N

Output

Print k_1,\ldots, and k_N resulting from deciding the nicknames of the N people by the procedure in the problem statement.

Sample Input 1

3
snuke
snuke
rng

Sample Output 1

1 2 1
  • First, he decides person 1's nickname.
    • Let k_1=1.
    • The k_1-time repetition of S_1 is snuke, which is nobody's nickname, so person 1's nickname is set to snuke.
  • Next, he decides person 2's nickname.
    • Let k_2=1.
    • The k_2-time repetition of S_2 is snuke, which is already a nickname of person 1, so increment k_2 by one to make it 2.
    • The k_2-time repetition of S_2 is snukesnuke, which is nobody's nickname, so person 2's nickname is set to snukesnuke.
  • Finally, he decides person 3's nickname.
    • Let k_3=1.
    • The k_3-time repetition of S_3 is rng, which is nobody's nickname, so person 3's nickname is set to rng.

Thus, k_1, k_2, and k_3 result in 1, 2, and 1, respectively.

Sample Input 2

4
aa
a
a
aaa

Sample Output 2

1 1 3 2
  • Person 1's nickname is set to aa.
  • Person 2's nickname is set to a.
  • Person 3's nickname is set to aaa, because a and aa are already nicknames of someone else.
  • Person 4's nickname is set to aaaaaa, because aaa is already a nickname of someone else.

Sample Input 3

5
x
x
x
x
x

Sample Output 3

1 2 3 4 5