Greatest Common Divisor

Problem Description

You have a ring with $n$ positive integers on it. You may cut the ring into $k$ segments, each containing one or more numbers.

For a cutting scheme, its "beauty" is defined as the greatest common divisor of the sums of the numbers in each segment. You want to maximize the beauty of the cutting scheme. For $k = 1, 2, \dots, n$, output the answer.

Input Format

The first line contains an integer $n$, the number of numbers on the ring.

The next line contains $n$ positive integers; the $i$-th number $a_i$ is the $i$-th number on the ring.

Output Format

Output $n$ lines; the $i$-th line is the maximum beauty when cut into $i$ segments.

Sample Input

7
2 3 3 3 3 3 3

Sample Output

20
5
2
2
1
1
1

Constraints

There are 10 test cases in total.

Test cases $1, 2$ satisfy $n \le 20$.

Test cases $3, 4, 5$ satisfy $a_i \le 5$.

For all data: $1 \le n \le 2000$, $1 \le a_i \le 5 \times 10^7$.

Hint

See the attached file.