snukesnuke

题目描述

高桥君要为人 $1,\ldots,N$ 这 $N$ 个人决定昵称。

第 $i$ 个人想要的昵称是 $S_i$。为了避免给多个人相同的昵称,他按以下方式决定昵称:

对于 $i=1,\ldots,N$,按顺序如下决定第 $i$ 个人的昵称:

• 将变量 $k_i$ 初始化为 $1$。
• 只要 $S_i$ 重复 $k_i$ 次得到的字符串是某个人的昵称,就不断将 $k_i$ 加 $1$。
• 将第 $i$ 个人的昵称设为 $S_i$ 重复 $k_i$ 次得到的字符串。

求为这 $N$ 个人决定昵称后,$k_1,\ldots,k_N$ 的值。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$
$\vdots$
$S_N$

输出格式

输出一行,包含按顺序排列的 $k_1,\ldots,k_N$,用空格分隔。

样例

3
snuke
snuke
rng

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$ 重复 $2$ 次得到的字符串是 snukesnuke,还不是任何人的昵称,所以第 $2$ 个人的昵称定为 snukesnuke。

最后决定第 $3$ 个人的昵称。

令 $k_3 = 1$。

$S_3$ 重复 $k_3$ 次得到的字符串是 rng,还不是任何人的昵称,所以第 $3$ 个人的昵称定为 rng。

因此,$k_1$、$k_2$、$k_3$ 分别变为 $1$、$2$、$1$。

4
aa
a
a
aaa

1 1 3 2

第 $1$ 个人的昵称定为 aa。

第 $2$ 个人的昵称定为 a。

第 $3$ 个人的昵称定为 aaa,因为 a 和 aa 已经是别人的昵称。

第 $4$ 个人的昵称定为 aaaaaa,因为 aaa 已经是别人的昵称。

5
x
x
x
x
x

1 2 3 4 5

数据范围

• $N \ge 1$
• $S_i$ 是由小写英文字母组成的长度至少为 $1$ 的字符串。
• $S_i$ 的长度之和至多为 $2\times 10^5$。