Problem Description

Score: $ 500 $ points

penguinman has a sequence $ A $ of length $ N $, but it is too large, so he decided to compress it to a length of $ K $.

Specifically, he will divide $ A $ into $ K $ consecutive subsequences $B_1, B_2, \ldots, B_K$, and then generate a new sequence $ C $ with elements being the sums of the elements in $B_1, B_2, \ldots, B_K$.

By the way, penguinman gets happier the larger the greatest common divisor (GCD) of all elements in a sequence $ X $ is.

By compressing the sequence optimally, what is the maximum GCD of the elements in the compressed sequence $ C $ for each $K = 1, 2, \ldots, N$?

Input Format

The input is given from the standard input in the following format:

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

Output Format

Output $ N $ lines. The $ i $-th line should contain the answer for $ K = i $. End each line with a newline character.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

6
3
1

Sample Input #2

6
10 36 28 91 58 11

Sample Output #2

234
3
2
2
1
1

Sample Input #3

10
48 33 57 91 70 63 51 100 300 234

Sample Output #3

1047
3
3
3
3
3
1
1
1
1

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分