B'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 <= i <= 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 . There are two integers on the first line -- the numbers n and q ( 1 <= q n <= q 5 cdot 10^5 , 1 <= q q <= q 5 cdot 10^5 ). On the second line, there are n integers -- the numbers a_1, a_2, ldots, a_n ( 1 <= q a_i <= q 10^8 ). On the third line, there are n integers -- the numbers b_1, b_2, ldots, b_n ( 1 <= q b_i <= q 10^8 ). On the fourth line, there are n integers -- the numbers c_1, c_2, ldots, c_n ( 1 <= q c_i <= q 10^9 ). On the fifth line, there are q integers -- the numbers d_1, d_2, ldots, d_q ( 0 <= q d_i <= q 10^{15} ). Print q integers -- the maximum value you can get for each of the q possible values d . 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$'...