De3b0o's MathModel Ideal Gift#11857
Given an array of size (all a_i are distinct) and queries, each query is a single integer .
For each query, you need to find the largest integer x \ge 1 such that for every (1 \le i \le n):
b_i \cdot x - a_i \le c, where b_i is the smallest integer such that b_i \cdot x > a_i. The value b_i is uniquely determined for every and depends on .
The first line contains two integers and (1 \le n,q \le 10^6) — the length of array and the number of queries.
The second line contains space-separated integers a_1, a_2, \ldots, a_n (1 \le a_i \le 5 \cdot 10^7) — the array .
Each of the following lines contains a single integer (1 \le c \le 10^{18}) — the value for the query.
For each query, print its answer on a separate line.
Example 1
Suppose a = [5, 10, 3, 2, 20].
For the first query c=5:
For x=7 the array is [1,2,1,1,3].
b_1 \cdot x - a_1 = 1 \cdot 7 - 5 = 2 \le 5
b_2 \cdot x - a_2 = 2 \cdot 7 - 10 = 4 \le 5
b_3 \cdot x - a_3 = 1 \cdot 7 - 3 = 4 \le 5
b_4 \cdot x - a_4 = 1 \cdot 7 - 2 = 5 \le 5
b_5 \cdot x - a_5 = 3 \cdot 7 - 20 = 1 \le 5
So x = 7 is correct, and there is no x > 7 that satisfies the conditions, so x = 7 is the answer.
Subtask 1 (10 points): (n,q,a_i,c \le 10)
Subtask 2 (10 points): (n,q,a_i,c \le 100)
Subtask 3 (20 points): (n,q,a_i,c \le 1000)
Subtask 4 (20 points): (n,a_i \le 2000)
Subtask 5 (20 points): (a_i \le 10^6; n,q \le 1000)
Subtask 6 (20 points): (a_i \le 10^6)
Subtask 7 (25 points): (a_i \le 10^7)
Subtask 8 (50 points): (a_i \le 2 \cdot 10^7)
Subtask 9 (125 points): (a_i \le 3.5 \cdot 10^7)
Subtask 10 (200 points): No additional constraints.