CF1973F Maximum GCD Sum Queries

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$$$.

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} $ ).

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 $ . 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.