Pinecones

It's about time that you show everyone your prowess at throwing pinecones.

You have collected $N$ pinecones from the NZOI camp, and the $i$th pinecone can initally be thrown to a height of $H_i$ meters. However, pinecones will weaken after each throw (since you aren't very good at catching them). Therefore, when throwing a pinecone again, it can only be thrown 1 meter lower than on its previous throw. When the height that a pinecone can be thrown to becomes 0, it breaks completely and cannot be thrown again. For example, if a pinecone can initially be thrown to a height of two meters, then the second time you throw this pinecone it can only reach a height of one meter. After this second throw the pinecone breaks.

Since you have a naturally inquisitive mind, you have imagined $Q$ scenarios. For the $j$th scenario, you would like to know the maximum possible combined height (in meters) of your throws if you are allowed at most $T_j$ throws in total. For each throw, you can use any pinecone that isn't completely broken. If all the pinecones are completely broken, you cannot perform any more throws.

Because all these scenarios are in your imagination, the height that each pinecone can be thrown resets to their initial height after each scenario.

Since the answer may be very large, for each scenario you should output the answer modulo $1{,}000{,}000{,}007$ (remainder after dividing the answer by $1{,}000{,}000{,}007$, which can be found with x % 1000000007 in most languages).

Note: If you're using a type-sensitive language such as C, C++, C# or Java, you should use 64-bit integer types to prevent integer overflow. 64-bit integer types include long long for C or C++, and long for C# or Java.

Input

• The first line contains two space-separated integers, $N$ and $Q$ — the number of pinecones you have and the number of scenarios you have imagined.
• The second line contains a list of space-separated integers, $H_1, H_2, ..., H_n$ — the heights at which the pinecones you collected can be initially thrown, in meters.
• For the next $Q$ lines, the $j$th of these lines contains a single integer, $T_j$.

Output

• You should output $Q$ lines. The $j$th of these lines should contain a single integer describing the maximum possible combined height after $T_j$ throws, modulo $1{,}000{,}000{,}007$.

Constraints

• $1 \leq N,Q \leq 10^5$
• $1 \leq H_i \leq 10^9$ for all $1 \leq i \leq N$
• $1 \leq T_j \leq 10^{12}$ for all $1 \leq j \leq Q$

Subtasks

• Subtask 1 (+15%): $Q = 1$ and $N \leq 1{,}000$ and $H_i \leq 1{,}000$ for all $1 \leq i \leq N$ and $T_j \leq 1{,}000$ for all $1 \leq j \leq Q$
• Subtask 2 (+25%): $Q = 1$ and $H_i \leq 10^5$ for all $1 \leq i \leq N$ and $T_j \leq 10^5$ for all $1 \leq j \leq Q$
• Subtask 3 (+30%): $H_i \leq 10^5$ for all $1 \leq i \leq N$
• Subtask 4 (+30%): No further constraints

Sample Explanation

Note that in all scenarios in both samples, the answer modulo 1,000,000,007 is the same as itself.

• Sample 1: In the 1st scenario, you can throw the second pinecone 1 time for $4$ meters and the third pinecone 1 time for $5$ meters, giving the maximum possible combined height of $9$ meters. In the 2nd scenario, you can throw the first pinecone 1 time for $2$ meters, the second pinecone 3 times for $4+3+2=9$ meters, the third pinecone 4 times for $5+4+3+2=14$ meters, and the fourth pinecone 2 times for $4+3=7$ meters, giving a combined height of $32$ meters. In the 3rd scenario, you can throw the second pinecone 2 times, the third pinecone 3 times, and the fourth pinecone 1 time for a combined height of $23$ meters.

• Sample 2: You can throw up to 10 times in the 1st (and only) scenario, but every pinecone will have broken completely before that. Therefore, by throwing every pinecone until it breaks, you can achieve the maximum possible combined height of $1+(2+1)+1=5$ meters.

NOTE

If you are using Python, select Python 3.6 (PyPy 7.3) among the language options when making a submission. Otherwise, your solution may not pass the time limit for some subtasks even if it is maximally efficient.