Background

“Ding-ling-ling.” With the ringing of the bell for the last subject of the Gaokao, three years of youth suddenly freeze at this moment. The joy of graduation cannot outweigh the sadness of parting; while looking forward to the future, we still remember the songs of the past. The laughter and tears of over a thousand days and nights all converge at the graduation party. Surely, this will be one of the most unforgettable moments in life.

Problem 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