Для \(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\).
Выходные данные
Выведите \(q\) целых чисел — максимальное значение, которое можно получить для каждого из \(q\) возможных значений \(d\).
Примечание
В первом запросе из первого примера нам вообще не разрешается делать никаких обменов, поэтому ответом будет \(\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\) монет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2 3
4 5 6
1 1 1
0 1 2 3
|
2 3 3 3
|
|
2
|
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
|
|
3
|
1 1
3
4
5
0
|
7
|