说明

众所周知 gzx 玩的游戏都非常的奇特，这次他又在玩一个有趣的游戏，这个游戏是一个讲究装备配置的游戏，并不是无脑选择战斗力更高的装备就可以变强的。

在这个游戏中，gzx 控制一个角色，这个角色总共可以装备 n 件 `装备` 和携带一种 `法印` ，编号为 1 ~ n，每件装备的战斗力分别为 a_1,a_2...a_n

游戏的战斗力计算方式特别有趣，并不是简单的将所有装备的数值相加。

在这个游戏中，一个角色的战斗力是所有装备战斗力的最大公因子。

而法印的效果则是为所有装备全部增加 x 点战斗力

比如原本有 4 件装备，战斗力分别为 [8,2,6,4] ，而携带的法印效果为战斗力 +2,则最终每件装备的战斗力为 [10,4,8,6]，最终玩家战斗力为 gcd(10,4,8,6) = 2

现在 gzx 已经配置好了 n 件装备，但是他有 m 种法印可以选择，他想知道携带每一种法印的最终战斗力，以此来选出最高战斗力的配置。

输入格式

输入第一行包含两个正整数 n,m 分别表示有 n 件装备和 m 种法印

输入第二行包含 n 个正整数 a_1,a_2...a_n 分别表示每一件装备的战斗力

输入第二行包含 m 个正整数 b_1,b_2...b_m 分别表示每一种法印增加的战斗力

对于 40% 的数据，1 <= n,m <= 2000

对于 100% 的数据，1 <= n,m <= 2 * 10^5, 1 <= a_i,b_i <= 10^{18}

输出格式

输出包含 m 个正整数，用空格隔开，依次表示选择每一种法印的最终战斗力

样例

3 3
49 121 217
2 23 1

3 24 2