A50152.无事之札

夏绯自初窥其史后，就为荆公革新之精神与意志所触动。她不禁想到：要提出如此广泛且深刻的革新，荆公在考察朝野诸般法度利弊上所花费的精力，又有多少呢？于是她提出了下面这个问题。

假设一个知识面为 $x$ 的人，考察一个属性为 $y$ 的法度，所需的精力为 $f(x, y) = \min \lbrace n \in \mathbb Z_{\ge 1} : y \mid nx \rbrace$。现有一个序列 $A = \lbrace a_1, a_2, \dots, a_n \rbrace$，表示本朝需要考察的 $n$ 种法度的属性。绯绯会基于此进行 $m$ 次询问，其中第 $i$ 次询问：一个知识面为 $b_i$ 的人，考察所有 $n$ 种法度，所需的精力之和；形式化地，即 $\sum_{j = 1}^n f(b_i, a_j)$。

第一行包含一个整数 $n$，表示 $A$ 的长度。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$，表示 $A$。

第三行包含一个整数 $m$，表示询问次数。

接下来 $m$ 行，第 $i$ 行包含一个整数 $b_i$，表示一次询问。

共 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次询问的精力之和。

数据范围

对于所有测试数据，保证：

• $1 \le n, m \le 5 \times 10^5$
• $1 \le a_i, b_j \le 10^7$

测试点分布

测试点编号	$n, m \le$	$a_i, b_i \le$	特殊性质
1	$10^3$	$10^7$	—
2	$5 \times 10^5$	$5 \times 10^3$	—
3-4	$10^5$	$10^7$	A1
5-6	$10^5$	$10^7$	A2
7-8	$10^5$	$10^5$	B0
9-11	$10^5$	$10^5$	B1
12-14	$10^5$	$10^5$	B2
15-16	$10^5$	$10^5$	C0
17-18	$10^5$	$10^5$	C1
19-20	$10^5$	$10^5$	C2
21-22	$10^5$	$10^5$	—
23-25	$5 \times 10^5$	$10^7$	—

特殊性质说明

• A1：所有$a_i$均为质数
• A2：所有$b_i$均为质数
• B0：$a_i = i$且$b_i = i$
• B1：$a_i = i$
• B2：$b_i = i$
• C0：所有$a_i$和$b_j$都是两个质数的乘积
• C1：所有$a_i$都是两个质数的乘积
• C2：所有$b_i$都是两个质数的乘积