103127: [Atcoder]ABC312 Ex - snukesnuke

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

问题描述

高桥要给$N$个人，第$1$个人到第$N$个人起昵称。

第$i$个人想要的昵称是$S_i$。为了避免给多个人起相同的昵称，他按照以下方法来决定他们的昵称：

• 按照顺序，对每个人$i=1,\ldots,N$，决定第$i$个人的昵称如下：
  • 将变量$k_i$初始化为$1$。
  • 当第$k_i$次重复的$S_i$是某人的昵称时，不断将$k_i$加$1$。
  • 将第$i$个人的昵称设为第$k_i$次重复的$S_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$。
  • 第$k_1$次重复的$S_1$是，这不是任何人的昵称，因此第$1$个人的昵称被设为。
• 接下来，他决定第$2$个人的昵称。
  • 令$k_2=1$。
  • 第$k_2$次重复的$S_2$是，这已经是第$1$个人的昵称，因此将$k_2$加$1$使其变为$2$。
  • 第$k_2$次重复的$S_2$是，这不是任何人的昵称，因此第$2$个人的昵称被设为。
• 最后，他决定第$3$个人的昵称。
  • 令$k_3=1$。
  • 第$k_3$次重复的$S_3$是，这不是任何人的昵称，因此第$3$个人的昵称被设为。

因此，$k_1$，$k_2$和$k_3$分别结果为$1$，$2$和$1$。

样例输入 2

4
aa
a
a
aaa

样例输出 2

1 1 3 2

• 第$1$个人的昵称被设为。
• 第$2$个人的昵称被设为。
• 第$3$个人的昵称被设为，因为和已经是其他人的昵称了。
• 第$4$个人的昵称被设为，因为已经是其他人的昵称了。