Mirko 是个派对狂人，因此他决定为他的朋友们举办无穷无尽的派对。为了满足派对的需求，他决定摆放 $N$ 张桌子，并在上面放上糖果。我们知道每张桌子上的糖果数量 $b_i$。在接下来的永恒时光中的第一天，Mirko 打算每张桌子邀请一位朋友；第二天，他会每张桌子邀请两位朋友；第三天，三位朋友…… 显然，一般地，在第 $k$ 天，他会为每张桌子邀请 $k$ 位朋友。

当他的朋友们进入房间后，每张桌子旁会坐下 $k$ 个人，他们会将桌上的糖果尽可能多地均分成 $k$ 份，并扔掉可能剩下的余数。糖果分配完毕后，由于嫉妒等各种原因，只有人均分到相同糖果数量的桌子之间才会聚在一起交流。Mirko 有着无穷无尽的时间来研究他派对上的社交动态。首先，他想知道以下问题的答案：给定一个介于 $1$ 和 $N$ 之间的 $s$，最早在第几天，会出现一个由恰好 $s$ 张桌子组成的交流群体？

像往常一样，Mirko 无法解决自己的问题，所以每隔几天他就会来找你，并询问在给定 $s$ 的情况下，所需的最小天数是多少。唉，他有永恒的时间来提问，但你没有。因此，你需要编写一个程序，输出对于每个 $s$（从 $1$ 到 $N$）Mirko 所需的答案。

请注意：在每次派对开始前，Mirko 都会重新补充每张桌子上的糖果，这意味着糖果供应量与第一次派对前相同。此外，在下一次派对开始之前，当前派对的所有人都会离开。

输入格式

第一行输入包含一个整数 $N$（$1 \le N \le 100$）。

第二行输入包含 $N$ 个整数，第 $i$ 个数表示第 $i$ 张桌子上的糖果数量。

这些数字均在区间 $[1, 10^8]$ 内。

输出格式

输出 $N$ 行，每行包含一个整数。

第 $s$ 行应包含由恰好 $s$ 张桌子组成的群体所需的最小天数，如果永远不会出现该大小的群体，则输出 -1。

子任务

在占总分 30% 的测试数据中，所有桌子上的糖果数量均不超过 $10^3$。

在另外占总分 30% 的测试数据中，所有桌子上的糖果数量均不超过 $10^6$。

样例

输入样例 1

5
11 10 9 6 4

输出样例 1

1
2
3
6
12

输入样例 2

3
5 5 5

输出样例 2

-1
-1
1

输入样例 3

8
12 16 95 96 138 56 205 84

输出样例 3

1
5
14
49
96
97
139
206

说明

样例 1 解释：

在第一天，每张桌子都只与自己交流，因此大小为 1 的群体的答案是 1。

在第二天，坐在第 1 张和第 2 张桌子旁的人人均分到 5 颗糖果并聚在一起交流，因此大小为 2 的群体的答案是 2。

在第三天，第 1、2、3 张桌子会聚在一起交流（因为他们的人均糖果数都是 3）。

在第六天，第 1、2、3、4 张桌子会聚在一起交流（因为他们现在的人均糖果数都是 1）。

最后，在第十二天，所有桌子都会聚在一起交流，因为所有人均分到的糖果数都是 0。

样例 2 解释：

所有桌子的人均糖果数始终相同，因此永远不会存在大小小于 3 的群体。