Description

After one rehearsal, the teacher was not very satisfied. Of course, taking each student's ID number to compute a greatest common divisor is clearly unreasonable. So the teacher assigned an ability value to each student. Now the problem becomes: choose $k$ students from $n$ students so that their synergy (defined as the greatest common divisor of the selected ability values) is maximized. However, there are too many programs, and the required number of people for each program is unknown. The teacher wants to know, for every possible $k$, the maximum achievable synergy. This is getting troublesome, so it is up to you.

Note: The greatest common divisor of a single number is the number itself.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ space-separated positive integers, representing each student's ability value.

Output Format

Output $n$ lines. The $i$-th line is the maximum synergy when $k = i$.

4
1 2 3 4

4
2
1
1

Hint

Source: lzn original.

Constraints

Let the maximum ability value in the input be $\textit{inf}$.

• For $20\%$ of the testdata, $n \leq 5$, $\textit{inf} \leq 10^3$.
• For another $30\%$ of the testdata, $n \leq 100$, $\textit{inf} \leq 10$.
• For $100\%$ of the testdata, $n \leq 10^4$, $\textit{inf} \leq 10^6$.

Translated by ChatGPT 5