CF1605E.Array Equalizer

Jeevan has two arrays $a$ and $b$ of size $n$. He is fond of performing weird operations on arrays. This time, he comes up with two types of operations:

• Choose any $i$ ($1 \le i \le n$) and increment $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$.
• Choose any $i$ ($1 \le i \le n$) and decrement $a_j$ by $1$ for every $j$ which is a multiple of $i$ and $1 \le j \le n$.

He wants to convert array $a$ into an array $b$ using the minimum total number of operations. However, Jeevan seems to have forgotten the value of $b_1$. So he makes some guesses. He will ask you $q$ questions corresponding to his $q$ guesses, the $i$-th of which is of the form:

• If $b_1 = x_i$, what is the minimum number of operations required to convert $a$ to $b$?

Help him by answering each question.

吉凡有两个长度为 $n$ 的数组 $a$ 和 $b$。他热衷于对数组执行各种奇怪的操作。这一次，他提出了两种类型的操作：

• 任选一个 $i$（$1 \le i \le n$），对所有满足 $j$ 是 $i$ 的倍数且 $1 \le j \le n$ 的下标 $j$，将 $a_j$ 加 $1$；
• 任选一个 $i$（$1 \le i \le n$），对所有满足 $j$ 是 $i$ 的倍数且 $1 \le j \le n$ 的下标 $j$，将 $a_j$ 减 $1$。

他希望用最少的总操作次数将数组 $a$ 变为数组 $b$。然而，吉凡似乎忘记了 $b_1$ 的值，于是他做了一些猜测。他将向你提出 $q$ 个问题，对应他的 $q$ 次猜测；其中第 $i$ 个问题的形式为：

• 若 $b_1 = x_i$，则将 $a$ 变为 $b$ 所需的最少操作次数是多少？

请回答每一个问题。

The first line contains a single integer $n$ $(1 \le n \le 2 \cdot 10^{5})$ — the size of arrays $a$ and $b$.

The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \le a_i \le 10^6)$.

The third line contains $n$ integers $b_1, b_2, ..., b_n$ $(1 \le b_i \le 10^6$ for $i \neq 1$; $b_1 = -1$, representing that the value of $b_1$ is unknown$)$.

The fourth line contains a single integer $q$ $(1 \le q \le 2 \cdot 10^{5})$ — the number of questions.

Each of the following $q$ lines contains a single integer $x_i$ $(1 \le x_i \le 10^6)$ — representing the $i$-th question.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^{5}$）—— 表示数组 $a$ 和 $b$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1 \le a_i \le 10^6$）。

第三行包含 $n$ 个整数 $b_1, b_2, ..., b_n$（当 $i \neq 1$ 时，$1 \le b_i \le 10^6$；而 $b_1 = -1$，表示 $b_1$ 的值未知）。

第四行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^{5}$）—— 表示询问的次数。

接下来的 $q$ 行中，每行包含一个整数 $x_i$（$1 \le x_i \le 10^6$）—— 表示第 $i$ 次询问。

Output $q$ integers — the answers to each of his $q$ questions.

输出 $q$ 个整数——即他对 $q$ 个问题的回答。

Consider the first test case.

• $b_1 = 1$: We need to convert $[3, 7] \rightarrow [1, 5]$. We can perform the following operations:

  $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[2, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 1}}$ $[1, 5]$

  Hence the answer is $2$.

• $b_1 = 4$: We need to convert $[3, 7] \rightarrow [4, 5]$. We can perform the following operations:

  $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$ $\xrightarrow[\text{increase}]{\text{i = 1}}$ $[4, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[4, 5]$

  Hence the answer is $4$.

• $b_1 = 3$: We need to convert $[3, 7] \rightarrow [3, 5]$. We can perform the following operations:

  $[3, 7]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{decrease}]{\text{i = 2}}$ $[3, 5]$

  Hence the answer is $2$.

考虑第一个测试用例。

• $b_1 = 1$：我们需要将 $[3, 7] \rightarrow [1, 5]$。可执行如下操作：

  $[3, 7]$ $\xrightarrow[\text{减少}]{\text{i = 1}}$ $[2, 6]$ $\xrightarrow[\text{减少}]{\text{i = 1}}$ $[1, 5]$

  因此答案为 $2$。

• $b_1 = 4$：我们需要将 $[3, 7] \rightarrow [4, 5]$。可执行如下操作：

  $[3, 7]$ $\xrightarrow[\text{减少}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{减少}]{\text{i = 2}}$ $[3, 5]$ $\xrightarrow[\text{增加}]{\text{i = 1}}$ $[4, 6]$ $\xrightarrow[\text{减少}]{\text{i = 2}}$ $[4, 5]$

  因此答案为 $4$。

• $b_1 = 3$：我们需要将 $[3, 7] \rightarrow [3, 5]$。可执行如下操作：

  $[3, 7]$ $\xrightarrow[\text{减少}]{\text{i = 2}}$ $[3, 6]$ $\xrightarrow[\text{减少}]{\text{i = 2}}$ $[3, 5]$

  因此答案为 $2$。