题目描述

你有一个环，环上有$n$个正整数。你能将环切成$k$段，每段包含一个或者多个数字。

对于一个切分方案，优美程度为每段数字和的最大公约数，你想使切分方案的优美程度最大，对于$k=1,2,\dots, n$输出答案。

输入格式

第一行一个整数$n$，表示环上的数字个数。

接下来一行包含$n$个正整数，第$i$个数$a_i$表示环上第$i$个数。

输出格式

输出$n$行，第$i$行表示切成$i$段时的最大优美程度。

样例输入1

7
2 3 3 3 3 3 3

样例输出1

20
5
2
2
1
1
1

样例输入输出2

见下发文件。

数据规模

共10个测试点。

测试点$1, 2$满足$n\leq 20$。

测试点$3, 4, 5$满足$a_i\leq 5$。

对于所有数据，满足$1\leq n\leq 2000, 1\leq a_i\leq 5\times 10^7$。