Question
Unique String Labeling
Eli has a list of N strings and wants to label them uniquely as he goes through each one. For each string Si in the list, he checks how many times it’s already appeared in the previous strings S1 to Si-1. If Si hasn’t appeared before, he leaves it unchanged. However, if it has appeared X times already, he appends (X) to Si to make it distinct, with X as a string. Can you help Eli modify and print each string to ensure every entry is uniquely labeled?
Input
The first line of the input contains a single integer N.
The next N lines contains N strings S1, S2, ...., SN.
Constraints
1 ≤ N ≤ 2 x 105
Si
The next N lines contains N strings S1, S2, ...., SN.
Constraints
1 ≤ N ≤ 2 x 105
Si
Output
Print N lines as specified in the Problem Statement.
Example
Sample Input
5
newfile
newfile
newfolder
newfile
newfolder
Sample Output
newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)
5
newfile
newfile
newfolder
newfile
newfolder
Sample Output
newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)