考古学家刚刚破译了金字塔墙壁上的象形文字。其中一面墙上的文字描述了 $N$ 个神圣数字。所有能被这些数字中至少一个整除的数字也都是神圣的。 另外 $M$ 面墙上的文字声称，第 $Q_i$ 小的神圣数字具有魔法属性。考古学家想知道哪些数字具有魔法属性。你能帮帮他们吗？

任务

给定 $N$ 个正整数 $A_1, A_2, \dots, A_N$ 和 $M$ 个正整数 $Q_1, Q_2, \dots, Q_M$。对于每个 $i \in \{1, 2, \dots, M\}$，求出能被 $A_1, A_2, \dots, A_N$ 中至少一个整除的第 $Q_i$ 小的正整数。

输入格式

第一行包含两个整数 $N$ 和 $M$。第二行包含空格分隔的整数 $A_1, A_2, \dots, A_N$。接下来有 $M$ 行，每行包含一个整数 $Q_i$。

数据范围

$1 \le N \le 15$，$1 \le M \le 50$。 对于所有 $i \in \{1, 2, \dots, N\}$，满足 $2 \le A_i \le 10^{18}$。 这些数字的乘积满足 $A_1 \cdot A_2 \cdot \dots \cdot A_N \le 10^{18}$。 对于所有 $i \in \{1, 2, \dots, M\}$，满足 $1 \le Q_i \le 10^{18}$。 输出中的每个数字均小于或等于 $10^{18}$。 此外，在 10% 的测试用例中，$Q_1, Q_2, \dots, Q_M \le 10^6$。 此外，在 30% 的测试用例中，$N \le 2$。

输出格式

输出 $M$ 行。第 $i$ 行应包含能被 $A_1, A_2, \dots, A_N$ 中至少一个整除的第 $Q_i$ 小的正整数。

样例

输入 1

5 5
2 5 7 10 11
1
2
3
10
20

输出 1

2
4
5
14
28

输入 2

2 1
70 100
5

输出 2

210