/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
penguinman は長さN の数列 A を持っていますが、サイズが大きすぎるので長さが K になるように圧縮することにしました。
具体的には、A を K 個の連続する部分列 B_1,\ B_2,\ldots,\ B_K に切り分けた上で、新たに (B_1 に含まれる要素の総和),\ (B_2 に含まれる要素の総和),\ldots,\ (B_K に含まれる要素の総和) を要素に持つ数列 C を生成することにしました。
ところで、penguinman はある数列 X を持っているとき、X の全要素の最大公約数が大きければ大きいほど嬉しくなります。
うまく数列を圧縮することで、圧縮したあとの数列 C に含まれる要素の最大公約数は最大でいくつになりますか？
K=1,\ 2,\ \ldots,\ N についてこの問題を解いてください。
制約
- 入力は全て整数である。
- 1\leq N\leq300
- 1\leq A_i\leq300
入力
入力は以下の形式で標準入力から与えられます。(10:38 修正)
\(N\) \(A_1\) \(A_2\) \(\ldots\) \(A_N\)
出力
N 行に渡って出力してください。 i 行目には K=i のときの答えを出力してください。 最後に改行してください。
入力例1
3 1 2 3
出力例1
6 3 1
K=1 のとき、B_1=\{1,\ 2,\ 3\} と切り分けるしかありません。圧縮後の数列 C は \{6\} となり、その最大公約数は 6 です。 K=2 のとき、B_1=\{1,\ 2\},\ B_2=\{3\} と切り分けるか B_1=\{1\},\ B_2=\{2,\ 3\} と切り分けるかの 2 通りがあります。 圧縮後の数列 C はそれぞれ \{3,\ 3\},\ \{1,\ 5\} となり、最大公約数は 3,\ 1 です。最大値を取っているのは前者の 3 なので、3 を出力します。 K=3 のとき、B_1=\{1\},\ B_2=\{2\},\ B_3=\{3\} と切り分けるしかありません。圧縮後の数列 C は \{1,\ 2,\ 3\} となり、その最大公約数は 1 です。
入力例2
6 10 36 28 91 58 11
出力例2
234 3 2 2 1 1
入力例3
10 48 33 57 91 70 63 51 100 300 234
出力例3
1047 3 3 3 3 3 1 1 1 1