Uniform Sleep Count Transformation

Bessie, the cow, is very excited because she finally has off‐line classes. Unfortunately, Farmer John is such a boring lecturer that she often dozes off during class. Farmer John notices Bessie’s inattentiveness and orders another student, Elsie, to record the number of times Bessie falls asleep in each class. There are N classes, and in the i^th class Bessie fell asleep a_i times. It is guaranteed that the total number of times Bessie sleeps over all classes does not exceed \(10^{18}\).

Elsie, who considers herself Bessie’s rival, wants Farmer John to believe that in every class Bessie dozed off exactly the same number of times. In other words, she wants the record to show the same number in every class, so that Farmer John will think that the problem was entirely Bessie’s fault rather than due to the occasional dull lecture.

Elsie is allowed only the following two types of modifications:

• Merge: Choose two classes and combine their records into one class. For example, if the record is [1,2,3,4,5] and she merges the second and third classes, the record becomes [1,5,4,5].
• Split: Choose one class and split its record into two classes with nonnegative integers that add up to the original value. For example, if the record is [1,5,4,5] and she splits the third class record of 4, she may obtain one of the following: [1,5,0,4,5], [1,5,1,3,5], [1,5,2,2,5], [1,5,3,1,5], or [1,5,4,0,5].

Elsie is given Q candidate numbers \(q_1, q_2, \ldots, q_Q\), each of which Bessie supposedly dislikes. For each candidate number \(q\), determine the minimum number of operations (merges and splits) required to modify the record so that every class shows exactly \(q\) (in every class).

Note: Since the operations only affect the partition of the total sleep count (which remains invariant), a necessary condition is that the total sleep count \(S = \sum_{i=1}^{N}a_i\) must be divisible by \(q\). In that case, the final record must contain exactly \(k = S/q\) classes, each with value \(q\). If \(S\) is not divisible by \(q\), output -1.

How can Elsie achieve the transformation with the minimum operations?

---

Explanation of the Solution Approach:

Since the two allowed operations (merging and splitting) conserve the total sleep count, the final array must have exactly \(k = S/q\) classes when \(q\) divides \(S\); otherwise, the transformation is impossible.

You can think of the transformation as re‐partitioning the initial sequence of records \(a = [a_1, a_2,\dots,a_N]\) into several new parts, each equal to \(q\). For each record:

• If \(a_i = q\), no operation is needed.
• If \(a_i > q\) and is divisible by \(q\) (say \(a_i = t\,q\)), you can split it into \(t\) parts at a cost of \(t-1\) splits.
• If \(a_i > q\) but is not divisible by \(q\) (i.e. \(a_i = t\,q + r\) with \(0 < r < q\)), you can first split off \(t\) full parts (costing \(t\) splits) and treat the remainder \(r\) together with other remainders via a merge operation.
• If \(a_i < q\), it can only be combined (merged) with other records. Grouping several such records so that their sum becomes \(q\) costs (number of records in the group - 1) merges.

Thus, if we denote for each record \(a_i\):

• For \(a_i \ge q\): Let \(t = \lfloor a_i / q \rfloor\). If \(a_i\) is divisible by \(q\), add \(t-1\) to the cost; otherwise add \(t\) to the cost and treat the remainder \(r = a_i \bmod q\) in a merge pool.
• For \(a_i < q\): Treat the entire \(a_i\) as a remainder.

Let the total splitting cost be the sum over records with \(a_i \ge q\) processed as above. For all records that contribute a remainder (either because \(a_i < q\) or due to the leftover when \(a_i\) is not divisible by \(q\)), let:

• count_R = number of such records
• R_sum = sum of the remainders

The remainders must be grouped into \(R_{sum} / q\) groups (each summing to \(q\)), and the optimal merge cost for these is count_R - (R_sum/q) (since merging a group of \(r\) records costs \(r-1\) operations). The final minimum cost is the sum of the splitting cost and the merging cost. Remember to output -1 if \(S \bmod q \ne 0\).

inputFormat

The first line contains two integers \(N\) and \(Q\) \((1 \le N \le 10^5,\; 1 \le Q \le 10^5)\) representing the number of classes and the number of candidate values respectively.

The second line contains \(N\) nonnegative integers \(a_1, a_2, \ldots, a_N\) \((0 \le a_i \le 10^{18})\) representing the number of times Bessie fell asleep in each class. It is guaranteed that \(\sum_{i=1}^{N} a_i \le 10^{18}\).

Then follow \(Q\) lines, each containing a candidate integer \(q\) \((1 \le q \le 10^{18})\).

outputFormat

For each candidate \(q\), output the minimum number of operations (merges and splits) required to transform the record so that every class has exactly \(q\). If it is impossible, output -1.

sample

5 3
1 2 3 4 5
5
3
1

2
4
10

</p>