题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 以及一个长度为 $m$ 的数列 $b_1, b_2, \ldots, b_m$。

对于数列 $b$ 的任意下标 $j(1 \le j \le m)$，你需要求出 $a_1 + b_j, a_2 + b_j, \ldots, a_n + b_j$ 的最大公约数。

输入格式

第一行，两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n,m \le 2 \cdot 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^{18})$，两两之间以一个空格分隔。

第三行，$m$ 个整数 $b_1, b_2, \ldots, b_m(1 \le b_j \le 10^{18})$，两两之间以一个空格分隔。

输出格式

输出共一行，包含 $m$ 个整数，两两之间以一个空格分隔。

其中第 $j(1 \le j \le m)$ 个整数表示 $a_1 + b_j, a_2 + b_j, \ldots, a_n + b_j$ 的最大公约数（即数列 $a$ 中的 $n$ 个元素各自均加上 $b_j$ 后，得到的数列中所有元素的最大公约数）。

4 4
1 25 121 169
1 2 7 23

2 3 8 24

说明/提示

样例解释

• $b_1 = 1$，$gcd(1+1, 25+1, 121+1, 169+1) = 2$
• $b_2 = 2$，$gcd(1+2, 25+2, 121+2, 169+2) = 3$
• $b_3 = 7$，$gcd(1+7, 25+7, 121+7, 169+7) = 8$
• $b_4 = 23$，$gcd(1+23, 25+23, 121+23, 169+23) = 24$

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 20; a_i, b_j \le 1000$
• 对于 $60\%$ 的数据，$n,m \le 2000; a_i, b_j \le 10^9$
• 对于 $100\%$ 的数据，$1 \le n,m \le 2 \cdot 10^5; 1 \le a_i, b_j \le 10^{18}$