Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F. Maximum GCD Sum Queries
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

For k positive integers x1,x2,,xk, the value gcd 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.

Examples
Input
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.