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.