题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

对于 $40\%$ 的数据，$1 \leq n,m \leq 2000$

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

样例输入

3 3
49 121 217
2 23 1

样例输出

3 24 2