Time Limit: 5.0 s

Memory Limit: 1024.0 MB

Description

Thakur has an array \(A\) of length \(N\).

He defines \(gcd(Gi)\) as the GCD of a group or a combination of any \(i\) elements of the array \(A\).

For every \(K\) from \(1\) to \(N\) find the maximum value of \(gcd(Gk)\)

Input

first line taken an integer \(N\) : length of the array
second line takes \(N\) integers \(A1,A2,A3 ...AN\)
\(1 <= N <= 40\)
\(0 <= Ai <= 10^5\)

Output

Print \(N\) integers in a single line

Sample

3
2 5 6

6 2 1 

there are 3 possible group of size 1, so
\(gcd(G1) = max(2,5,6) = 6\)

there are 3 possible group of size 2, so
\(gcd(G2) = max(gcd(2,5),gcd(2,6),gcd(5,6)) = max(1,2,1) = 2\)

there are only one possible group of size 3, so
\(gcd(G3) = max(gcd(2,5,6)) = 1\)