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\mathrm{\%}$ of points, we can take advantage of some monotonic properties. Observe that as ${\epsilon }_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^{\prime }$ such that $\frac{C_i{s}_n+1.0s_c}{NM}\ge {\epsilon }_i$. Rearranging, we find that $C_i\ge \frac{NM{\epsilon }_i-1.0s_c}{s_n}$. Let's call $NM{\epsilon }_i-1.0s_c$ our target sum, $t$.

We then process the queries in ascending ${\epsilon }_i$. For each query $i$, we know that $C_i^{\prime }$ must be at least $\lceil \frac{t}{s_n}\cdot {10}^6\rceil$. However, setting $C_i^{\prime }$ to this value may result in some of the values clipping and the true $C_i^{\prime }$ being larger. Thus, as long as the elements at the front of the queue are clipped by our current $C_i^{\prime }$, we will pop them off and recalculate $s_n$, $s_c$, and $C_i^{\prime }$. Once we have found a $C_i^{\prime }$ 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}^{\prime }=\lceil \frac{t-1.0}{s_n-b_{front}}\cdot {10}^6\rceil$ is calculated, it is smaller than the previous $C_{pre}^{\prime }=\lceil \frac{t}{s_n}\cdot {10}^6\rceil$. (One such set of values from the test data is $t=25105059110$, $s_c=22570341993$, and $b_{front}=899035$.) How is this possible if $C$ is supposed to be monotonically increasing?

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

Time Complexity: $\mathcal{O}(NM\log (NM)+Q\log Q)$