给定一个由正整数组成的数组 A，对于其所有前缀子数组 A[1\dots i]，询问：
最多可以执行一次如下操作：
任意选定一个正整数 k ，将数组中的值都增加 k。
最大化操作后数组的 GCD（最大公约数）。求所得的 最大 GCD。
若答案可以任意大，输出 0。
注意每个前缀子数组的询问是独立的。
输入
数据第一行为一个正整数 N(2 \leq N \leq 10^5)，表示数组的长度。
第二行给出 N 个由空格隔开的整数 A_i (1 \leq A_i \leq 10^{18})，表示所给数组。
输出
输出一行共 N 个由空格隔开的整数，表示 A 的 N 个前缀数组的答案。
样例
| 标准输入 复制文本 |
5 1 9 1 9 8 |
| 标准输出 复制文本 |
0 8 8 8 1 |
提示
主播造样例尽力了 1_01
08881=114\times 5 \times 14 +((1+1)\times 451-4+11\times (-4)+51 -4)
第一个前缀数组只有一个数 1 时，选任意的 k 可以使最大 GCD 为 k+1，故答案为无穷大。
随后三个前缀数组中的数组成的集合都为 {1,9}，选择 k=15，得到 \gcd(16,24)=8。可以证明不存在使得答案严格更大的 k。