Maximum Synergy

In a rehearsal the teacher wasn’t satisfied with the performance when the selection was made by student numbers. Therefore, the teacher assigned each student an ability value. Now, the problem becomes: from n students, choose exactly k students such that their synergy level, defined as the greatest common divisor (i.e., \(\gcd\)) of their ability values, is maximized.

Since different programs might require different numbers of students, the teacher wants to know the maximum achievable synergy level for each possible team size \(k\) (where \(1 \le k \le n\)). Note that the \(\gcd\) of a single number is the number itself.

Example: If the ability values are [4, 6, 8, 10] then:

• For \(k=1\), the maximum synergy is \(10\) (by choosing the student with ability 10).
• For \(k=2\), one optimal choice is [4, 8] with \(\gcd(4,8)=4\).
• For \(k=3\), every three-student choice gives a \(\gcd\) of at most 2.
• For \(k=4\), the \(\gcd(4,6,8,10)=2\).

Your task is to compute and output n numbers, where the \(k\)-th number is the maximum possible synergy level when selecting exactly \(k\) students.

inputFormat

The first line contains a single integer \(n\) (the number of students). The second line contains \(n\) space-separated positive integers representing the ability values of the students.

\(1 \leq n \leq 10^5\); ability values are positive integers.

outputFormat

Output \(n\) space-separated integers. The \(k\)-th integer should be the maximum synergy level (i.e. maximum \(\gcd\)) achievable by any group of exactly \(k\) students.

sample

3
1 2 3

3 1 1