Hide

Problem I
Variable Names

Languages en sv

Nikolaj has been programming for many years, but never really understood the point of writing readable code. Nikolaj’s variable names are always $c_1$, $c_2$, $c_3$, etc. Sometimes Nikolaj wants to declare a new variable called $c_ i$, but the name $c_ i$ may already be taken. When that happens he tries the names $c_{2i}$, $c_{3i}$, etc., until he finds a name that is not already taken.

Write a program that given a list of $N$ variable names Nikolaj wants to use, determines the names he ends up choosing using the above strategy.

Input

The first line contains an integer $N$, the number of variables, where $1 \leq N \leq 2 \cdot 10^5$. Each of the following $N$ lines contains an integer $x$ with $1 \leq x \leq 10^4$. This means that Nikolaj wants to declare a new variable called $c_ x$. Nikolaj declares the variables in input order.

Output

For each of the $N$ integers $x$, print $y$ such that Nikolaj created the variable $c_ y$.

Explanation of Sample Input

In Sample Input $1$, the following will happen:

  1. Variable $c_1$ is declared.

  2. Variable $c_3$ is declared.

  3. Nikolaj would like to declare $c_1$, but that’s taken, so he declares $c_2$.

  4. Nikolaj would like to declare $c_2$, but that’s taken, so he declares $c_4$.

  5. Nikolaj would like to declare $c_1$, but that’s taken, so he declares $c_5$.

  6. Nikolaj would like to declare $c_5$, but that’s taken, so he declares $c_{10}$.

  7. Nikolaj would like to declare $c_5$, but that’s taken, so he declares $c_{15}$.

Sample Input 1 Sample Output 1
7
1
3
1
2
1
5
5
1
3
2
4
5
10
15

Please log in to submit a solution to this problem

Log in