这是一个鲜为人知的故事：年轻的卡尔·弗里德里希·高斯（Carl Friedrich Gauss）在课堂上总是坐不安稳，于是他的老师给他布置了一个任务来让他有事可做。

老师给了他一个正整数序列 $F(1), F(2), \dots, F(K)$。对于 $t > K$，我们认为 $F(t) = 0$。此外，老师还给了他一组幸运数以及每个幸运数的价格。如果 $X$ 是一个幸运数，则 $C(X)$ 表示它的价格。

最初，黑板上写着一个正整数 $A$。在每一步操作中，卡尔必须执行以下操作之一：

• 如果当前黑板上写着的数是 $N$，那么卡尔可以写下它的一个小于 $N$ 的约数 $M$ 来代替 $N$。如果他写下了数字 $M$，则该步操作的价格为 $F(d(N / M))$，其中 $d(N/M)$ 表示正整数 $N/M$ 的约数个数（包括 $N/M$ 本身）。
• 如果 $N$ 是一个幸运数，卡尔可以把这个数留在黑板上，该步操作的价格为 $C(N)$。

卡尔必须恰好进行 $L$ 步操作。在完成所有操作后，黑板上写着的数字必须是 $B$。我们用 $G(A, B, L)$ 表示卡尔达成这一目标所需的最小总价格。

如果无法通过恰好 $L$ 步操作达成目标，我们定义 $G(A, B, L) = -1$。

老师给卡尔提出了 $Q$ 个询问。在每个询问中，卡尔会得到数字 $A$ 和 $B$，并且必须计算值 $G(A, B, L_1) + G(A, B, L_2) + \dots + G(A, B, L_M)$，其中数字 $L_1, \dots, L_M$ 对所有询问都是相同的。

输入格式

第一行包含一个正整数 $K$（$1 \le K \le 10\,000$）。

第二行包含 $K$ 个正整数 $F(1), F(2), \dots, F(K)$，它们均小于或等于 $1\,000$。

第三行包含一个正整数 $M$（$1 \le M \le 1\,000$）。

第四行包含 $M$ 个正整数 $L_1, L_2, \dots, L_M$，它们均小于或等于 $10\,000$。

第五行包含一个正整数 $T$，表示幸运数的总数（$1 \le T \le 50$）。

接下来的 $T$ 行，每行包含两个数字 $X$ 和 $C(X)$，表示 $X$ 是一个幸运数，且其价格为 $C(X)$（$1 \le X \le 1\,000\,000$，$1 \le C(X) \le 1\,000$）。

每个幸运数最多出现一次。

接下来的下一行包含一个正整数 $Q$（$1 \le Q \le 50\,000$）。

接下来的 $Q$ 行，每行包含两个正整数 $A$ 和 $B$（$1 \le A, B \le 1\,000\,000$）。

输出格式

输出 $Q$ 行。第 $i$ 行包含任务中定义的第 $i$ 个询问的答案。

样例

输入样例 1

4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2

输出样例 1

7

输入样例 2

3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68

输出样例 2

118
-2

输入样例 3

3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1

输出样例 3

16
66

说明

样例 1 说明：

$L_1 = 1$，因此卡尔只能进行恰好一次操作——将数字 $4$ 替换为数字 $2$，所以 $G(4, 2, 1) = F(d(2)) = 1$。

$L_2 = 2$，因此卡尔有两种选择：

• 他可以将数字 $4$ 替换为数字 $2$，然后保留数字 $2$（因为 $2$ 是一个幸运数），这样他支付的价格为 $F(d(4/2)) + C(2) = 1 + 5 = 6$。
• 他可以在第一步中保留数字 $4$，并在第二步中将其替换为数字 $2$，这样价格为 $C(4) + F(d(4/2)) = 10 + 1 = 11$。

第一种选择的花费更少，因此 $G(4, 2, 2) = 6$。

询问的答案为 $G(4, 2, 1) + G(4, 2, 2) = 7$。