Make Unique Variables

You are given a list of variable names. In order to avoid conflicts, if a variable name appears more than once, you must modify the duplicates by appending the smallest possible positive integer such that all variable names become unique. For example, if the name "apple" appears three times, the output should be "apple", "apple1", and "apple2" in the order they appear.

Formally, if we denote the original list as \(a_1, a_2, \ldots, a_n\), then the resulting list \(b_1, b_2, \ldots, b_n\) should satisfy that \(b_i\) is equal to \(a_i\) if \(a_i\) has not appeared before; otherwise, let \(k\) be the smallest positive integer such that \(a_i\)+\(k\) has not appeared earlier, and set \(b_i = a_i\)+\(k\).

inputFormat

The input begins with an integer \(n\) (\(0 \le n \le 10^5\)) representing the number of variable names. The following \(n\) lines each contain a single variable name, which is a non-empty string of at most 20 characters.

outputFormat

Output a single line containing \(n\) space-separated variable names, in the same order as the input, after ensuring all are unique as described above.

3
apple
banana
apple

apple banana apple1