[ABC312Ex] snukesnuke

## 题目翻译 高桥君需要给 $ N $ 个人取一个绰号。 第 $ i $ 个人希望将其绰号设为 $ S_i $。为了避免给多个人取相同的绰号，高橋君决定采用以下步骤为这 $ N $ 个人分别确定绰号： - 对于 $ i=1,\ldots,N $，按以下步骤来确定第 $ i $ 个人的绰号： - 将变量 $ k_i $ 设为 $ 1 $。 - 当“将 $ S_i $ 重复 $ k_i $ 次得到的字符串”已经是某人的绰号时，不断增加 $ k_i $ 的值，直到找到一个没有被使用过的绰号。 - 将“将 $ S_i $ 重复 $ k_i $ 次得到的字符串”设为第 $ i $ 个人的绰号。 请计算出确定了 $ N $ 个人的绰号后的 $ k_1,\ldots,k_N $。

[problemUrl]: https://atcoder.jp/contests/abc312/tasks/abc312_h 高橋君は人 $ 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 $ $ S_1 $ $ \vdots $ $ S_N $

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

3
snuke
snuke
rng

1 2 1

4
aa
a
a
aaa

1 1 3 2

5
x
x
x
x
x

1 2 3 4 5

### 制約 - $ N\ \geq\ 1 $ - $ S_i $ は英小文字のみからなる、長さ $ 1 $ 以上の文字列 - $ S_i $ の長さの総和は $ 2\times\ 10^5 $ 以下 ### Sample Explanation 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 $ となります。 ### Sample Explanation 2 \- 人 $ 1 $ のあだ名は `aa` になります。 - 人 $ 2 $ のあだ名は `a` になります。 - 人 $ 3 $ のあだ名は、`a`, `aa` がすでに他の人のあだ名なので、`aaa` になります。 - 人 $ 4 $ のあだ名は、`aaa` がすでに他の人のあだ名なので、`aaaaaa` になります。