Một người dùng lần lượt tạo ~N~ folder trên máy họ, folder thứ ~i~ được đặt tên là ~S_i~ là một xâu chỉ bao gồm các chữ cái Latin. Do sẽ có những folder trùng tên, máy tính sẽ lưu tên các folder như sau:

• Nếu tên folder ~S_i~ chưa được dùng, máy tính sẽ lưu bằng tên đó.
• Ngoài ra, với ~X~ là số lần ~S_i~ đã xuất hiện trước đó, máy sẽ lưu folder đó dưới cái tên ~S_i~ ~+~ ~(X)~.

Cho ~N~ xâu được dùng làm tên folder, hãy cho biết tên của ~N~ folder này sau khi lưu.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ (~1 \leq N \leq 10^5~) duy nhất là số lượng xâu.
• ~N~ dòng tiếp theo, dòng thứ ~i~ là xâu ~S_i~ (~1 \leq |S_i| \leq 10~).

Output

Ghi ra ~N~ dòng, dòng thứ ~i~ là tên của folder thứ ~i~ sau khi lưu trên máy.

Sample input

5
newfile
newfile
newfolder
newfile
newfolder

Sample output

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Subtask

• ~30\%~ số test có ~1 \leq N \leq 100~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.