著名的 Berland 分数工厂处理各种分数：它可以将它们相乘、拆解成碎片，并在不同的数制之间进行转换。

但今天每个人都忘记了工作，因为今天是一个特殊的日子：官方供应商给工厂带来了一个极其巨大的分数。它是：

$$Q = \frac{a_1 \cdot a_2 \cdot \dots \cdot a_n}{b_1 \cdot b_2 \cdot \dots \cdot b_m}$$

员工们很快对 $Q$ 产生了兴趣。他们甚至决定计算它的值！不幸的是，他们没有足够的计算能力。幸运的是，今天你来到 Berland 分数工厂参加面试。所以现在这是你的任务，只要解决了它，你就保证能得到这份工作。

为了获得更高的精度，员工们要求你计算 $Q$ 对 $M$ 取模的值，但要重复进行。更准确地说，对于 $1 \le l \le k$，你需要输出 $Q \pmod{M_l}$，其中 $M_l$ 是大于 1 的整数。

现在，让我们形式化计算 $Q \pmod M$ 的过程。首先，我们将 $Q$ 的分子和分母中的所有因子进行质因数分解。然后，我们“约去”所有重复的质因子：只要存在一个质数 $p$ 和两个正整数 $A$ 和 $B$，使得 $Q = \frac{p \cdot A}{p \cdot B}$，我们就将分子和分母同时除以 $p$。在此之后，我们“公平地”计算 $Q \pmod M$ 的值。通常，我们假设 $\frac{1}{x} \pmod M$ 等于满足 $0 \le y < M$ 且 $x \cdot y \equiv 1 \pmod M$ 的 $y$。如果不存在这样的 $y$，我们称 $x$ 是不可逆的。

如果在模 $M$ 的计算过程中，你需要对一个不可逆的值求逆，只需输出 “DIVISION BY ZERO”。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5000$)，分别表示分数分子和分母中因子的总数。

第二行包含 $n$ 个整数 $a_i$ ($1 \le a_i \le 10^{18}$)。

第三行包含 $m$ 个整数 $b_j$ ($1 \le b_j \le 10^{18}$)。

下一行包含一个整数 $k$ ($1 \le k \le 50$)，表示查询的总数。

接下来的 $k$ 行，每行包含一个整数 $M_l$ ($2 \le M_l \le 10^{18}$)。

输出格式

输出 $k$ 行。第 $l$ 行必须包含一个整数（即 $Q \pmod{M_l}$，如果该值对于 $l$ 有定义），否则输出字符串 “DIVISION BY ZERO”（不含引号）。

样例

输入 1

3 2
8 11 14
9 12
4
8
9
10
11

输出 1

4
DIVISION BY ZERO
4
0