F. Запросы максимальной суммы НОД
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для $$$k$$$ целых положительных чисел $$$x_1, x_2, \ldots, x_k$$$ значение $$$\gcd(x_1, x_2, \ldots, x_k)$$$ является наибольшим общим делителем чисел $$$x_1, x_2, \ldots, x_k$$$ — наибольшим целым числом $$$z$$$ таким, что все числа $$$x_1, x_2, \ldots, x_k$$$ делятся на $$$z$$$.

Вам даны три массива $$$a_1, a_2, \ldots, a_n$$$, $$$b_1, b_2, \ldots, b_n$$$ и $$$c_1, c_2, \ldots, c_n$$$ длины $$$n$$$, содержащие положительные целые числа.

У вас также есть автомат, который позволяет вам менять местами $$$a_i$$$ и $$$b_i$$$ для любого $$$i$$$ ($$$1 \le i \le n$$$). Каждый обмен стоит вам $$$c_i$$$ монет.

Найдите максимальное возможное значение $$$$$$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)\text{,}$$$$$$ которое вы можете получить, поменяв местами несколько элементов, и заплатив при этом не более $$$d$$$ монет в сумме. Количество монет у вас меняется, поэтому найдите ответ на этот вопрос для каждого из $$$q$$$ возможных значений $$$d_1, d_2, \ldots, d_q$$$.

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

В первой строке находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$, $$$1 \leq q \leq 5 \cdot 10^5$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^8$$$).

В третьей строке находятся $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^8$$$).

В четвертой строке находятся $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$).

В пятой строке находятся $$$q$$$ целых чисел $$$d_1, d_2, \ldots, d_q$$$ ($$$0 \leq d_i \leq 10^{15}$$$).

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

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

Примеры
Входные данные
3 4
1 2 3
4 5 6
1 1 1
0 1 2 3
Выходные данные
2 3 3 3
Входные данные
5 5
3 4 6 8 4
8 3 4 9 3
10 20 30 40 50
5 55 13 1000 113
Выходные данные
2 7 3 7 7
Входные данные
1 1
3
4
5
0
Выходные данные
7
Примечание

В первом запросе из первого примера нам вообще не разрешается делать никаких обменов, поэтому ответом будет $$$\gcd(1, 2, 3) + \gcd(4, 5, 6) = 2$$$. Во втором запросе одним из способов достижения оптимального значения является обмен $$$a_2$$$ и $$$b_2$$$, тогда ответом будет $$$\gcd(1, 5, 3) + \gcd(4, 2, 6) = 3$$$.

Во втором запросе из второго примера оптимально сделать обмены на позициях $$$1$$$ и $$$3$$$, тогда ответом будет $$$\gcd(3, 3, 6, 9, 3) + \gcd(8, 4, 4, 8, 4) = 7$$$, и нам суммарно придется заплатить $$$40$$$ монет.