311356: CF1973F. Maximum GCD Sum Queries

F. Maximum GCD Sum Queriestime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

For $k$ positive integers $x_1, x_2, \ldots, x_k$, the value $\gcd(x_1, x_2, \ldots, x_k)$ is the greatest common divisor of the integers $x_1, x_2, \ldots, x_k$ — the largest integer $z$ such that all the integers $x_1, x_2, \ldots, x_k$ are divisible by $z$.

You are given three arrays $a_1, a_2, \ldots, a_n$, $b_1, b_2, \ldots, b_n$ and $c_1, c_2, \ldots, c_n$ of length $n$, containing positive integers.

You also have a machine that allows you to swap $a_i$ and $b_i$ for any $i$ ($1 \le i \le n$). Each swap costs you $c_i$ coins.

Find the maximum possible value of $$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$$ that you can get by paying in total at most $d$ coins for swapping some elements. The amount of coins you have changes a lot, so find the answer to this question for each of the $q$ possible values $d_1, d_2, \ldots, d_q$.

Input

There are two integers on the first line — the numbers $n$ and $q$ ($1 \leq n \leq 5 \cdot 10^5$, $1 \leq q \leq 5 \cdot 10^5$).

On the second line, there are $n$ integers — the numbers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^8$).

On the third line, there are $n$ integers — the numbers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^8$).

On the fourth line, there are $n$ integers — the numbers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^9$).

On the fifth line, there are $q$ integers — the numbers $d_1, d_2, \ldots, d_q$ ($0 \leq d_i \leq 10^{15}$).

Output

Print $q$ integers — the maximum value you can get for each of the $q$ possible values $d$.

ExamplesInput

3 4
1 2 3
4 5 6
1 1 1
0 1 2 3

Output

2 3 3 3 

Input

5 5
3 4 6 8 4
8 3 4 9 3
10 20 30 40 50
5 55 13 1000 113

Output

2 7 3 7 7 

Input

1 1
3
4
5
0

Output

7 

Note

In the first query of the first example, we are not allowed to do any swaps at all, so the answer is $\gcd(1, 2, 3) + \gcd(4, 5, 6) = 2$. In the second query, one of the ways to achieve the optimal value is to swap $a_2$ and $b_2$, then the answer is $\gcd(1, 5, 3) + \gcd(4, 2, 6) = 3$.

In the second query of the second example, it's optimal to perform swaps on positions $1$ and $3$, then the answer is $\gcd(3, 3, 6, 9, 3) + \gcd(8, 4, 4, 8, 4) = 7$ and we have to pay $40$ coins in total.

题目大意：给定三个长度为n的数组a[], b[], c[]，你可以通过支付c[i]的代价来交换a[i]和b[i]。求通过支付最多d的代价，所能得到的$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$的最大值。对于每个可能的d值，输出答案。

输入数据格式：
- 第一行：两个整数n和q（1≤n≤5×10^5, 1≤q≤5×10^5），分别表示数组长度和查询次数。
- 第二行：n个整数，表示数组a[]。
- 第三行：n个整数，表示数组b[]。
- 第四行：n个整数，表示数组c[]。
- 第五行：q个整数，表示每个查询的d值。

输出数据格式：
- q个整数，表示每个d值对应的答案。题目大意：给定三个长度为n的数组a[], b[], c[]，你可以通过支付c[i]的代价来交换a[i]和b[i]。求通过支付最多d的代价，所能得到的$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$的最大值。对于每个可能的d值，输出答案。 输入数据格式： - 第一行：两个整数n和q（1≤n≤5×10^5, 1≤q≤5×10^5），分别表示数组长度和查询次数。 - 第二行：n个整数，表示数组a[]。 - 第三行：n个整数，表示数组b[]。 - 第四行：n个整数，表示数组c[]。 - 第五行：q个整数，表示每个查询的d值。 输出数据格式： - q个整数，表示每个d值对应的答案。