E. Уравнитель массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Jeevan есть два массива $$$a$$$ и $$$b$$$ размером $$$n$$$. Он любит выполнять странные операции над массивами. На этот раз он придумал два типа операций:

  • Выберите любое $$$i$$$ ($$$1 \le i \le n$$$) и увеличьте $$$a_j$$$ на $$$1$$$ для каждого $$$j$$$, которое кратно $$$i$$$ и $$$1 \le j \le n$$$.
  • Выберите любое $$$i$$$ ($$$1 \le i \le n$$$) и уменьшите $$$a_j$$$ на $$$1$$$ для каждого $$$j$$$, которое кратно $$$i$$$ и $$$1 \le j \le n$$$.

Он хочет преобразовать массив $$$a$$$ в массив $$$b$$$, используя минимальное общее количество операций. Однако Jeevan, похоже, забыл значение $$$b_1$$$. Поэтому он делает некоторые предположения. Он задаст вам $$$q$$$ вопросов, соответствующих его $$$q$$$ догадкам, $$$i$$$-я из которых имеет вид:

  • Если $$$b_1 = x_i$$$, то какое минимальное количество операций требуется для преобразования $$$a$$$ в $$$b$$$?

Помогите ему, ответив на каждый вопрос.

Входные данные

Первая строка содержит одно целое число $$$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$$$ $$$(1 \le b_i \le 10^6$$$ для $$$i \neq 1$$$; $$$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$$$-й вопрос.

Выходные данные

Выведите $$$q$$$ целых чисел  — ответы на каждый из его $$$q$$$ вопросов.

Примеры
Входные данные
2
3 7
-1 5
3
1
4
3
Выходные данные
2
4
2
Входные данные
6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4
Выходные данные
10
29
9
Примечание

Рассмотрим первый пример.

  • $$$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$$$.