AT_abc312_h [ABC312Ex] snukesnuke

[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 $ をこの順に空白区切りで出力せよ。

### 制約 - $ 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` になります。