This problem was greatly inspired by this DMOPC problem. The first subtask can be solved in the same manner as it.

For the remaining ~90\%~ of points, we can take advantage of some monotonic properties. Observe that as ~\varepsilon_i~ increases, the number of elements that become "clipped" monotonically increases.

Thus, we can push the elements in the grid into a queue in descending ~b_{i, j}~. We maintain the current sum ~s_n~ of non-clipped elements and the number ~s_c~ of clipped elements. For each query ~i~, we want to find the first ~C'_i~ such that ~\frac{C_is_n + 1.0s_c}{NM} \geq \varepsilon_i~. Rearranging, we find that ~C_i \geq \frac{NM \varepsilon_i - 1.0s_c}{s_n}~. Let's call ~NM \varepsilon_i - 1.0s_c~ our target sum, ~t~.

We then process the queries in ascending ~\varepsilon_i~. For each query ~i~, we know that ~C'_i~ must be at least ~\lceil\frac{t}{s_n} \cdot 10^6\rceil~. However, setting ~C'_i~ to this value may result in some of the values clipping and the true ~C'_i~ being larger. Thus, as long as the elements at the front of the queue are clipped by our current ~C'_i~, we will pop them off and recalculate ~s_n~, ~s_c~, and ~C'_i~. Once we have found a ~C'_i~ that does not clip any additional elements, we have our answer. As each of the ~NM~ elements is popped at most once, the overall complexity of this stage is ~\mathcal O(NM + Q)~.

However, there is one thing to watch out for. There are certain values for ~t~, ~s_c~, and the element at the front of the queue ~b_{front}~ such that when ~C'_{new} = \lceil\frac{t - 1.0}{s_n - b_{front}} \cdot 10^6 \rceil~ is calculated, it is smaller than the previous ~C'_{pre} = \lceil\frac{t}{s_n} \cdot 10^6 \rceil~. (One such set of values from the test data is ~t = 25\,105\,059\,110~, ~s_c = 22\,570\,341\,993~, and ~b_{front} = 899\,035~.) How is this possible if ~C~ is supposed to be monotonically increasing?

The problem lies with the ceiling function. In such cases, ~C'_{pre} = \frac{t}{s_n} \cdot 10^6~ does not cause ~b_{front}~ to clip, but ~C'_{pre} = \lceil\frac{t}{s_n} \cdot 10^6\rceil~ does. This causes us to pop ~b_{front}~ off the queue and calculate ~C'_{new}~, which in these cases turns out to be less than ~C'_{pre}~. However, since we needed ~C'~ to be at least ~C'_{pre}~ in order to clip ~b_{front}~, the correct answer would be ~C'_{pre}~, not ~C'_{new}~! These cases are a common source of WA's but are easily dealt with by updating ~C'_{cur}~ to ~\max(C'_{pre}, C'_{new})~ rather than replacing it with ~C'_{new}~.

Time Complexity: ~\mathcal O(NM \log(NM) + Q \log Q)~