P8231 [AGM 2022 Qualification Round] Farm

You are a capitalist, managing a grid-shaped field of size $n \times m$. Initially, the cell in row $i$ and column $j$ contains $a_{i,j}$ units of wheat. On this field, you have marked $Q$ rectangles, each representing a farm (different farms may overlap). The amount of wheat of a farm equals the sum of wheat over all cells inside the rectangle. A farm makes a profit if and only if the total wheat in this farm is greater than or equal to the required amount $b_i$. Unfortunately, there will be heavy rain for $T$ consecutive days. Each day, the wheat amount in some cells decreases. For each farm, determine for how many days it can make a profit. If it is still profitable after $T$ days, output $-1$.

The first line contains two integers $n, m$. The next $n$ lines each contain $m$ integers $a_{i,j}$. The next line contains an integer $Q$. The following $Q$ lines each contain five numbers $l, r, L, R, b$, representing the top-left coordinate, the bottom-right coordinate, and the required wheat amount for profit of the $i$-th farm. The next line contains an integer $T$. The following input consists of $T$ blocks. In each block, first an integer $p$ is given, indicating the events on that day, followed by $p$ lines. Each of these lines contains three integers $x, y, z$, meaning the wheat in cell $(x, y)$ decreases by $z$.

Output one line with $Q$ integers, representing the answers.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 500$, $1 \leq Q \leq 50000$, $0 \leq a_{i,j} \leq 10^9$, $1 \leq l < L \leq n$, $1 < r < R \leq m$, $0 \leq b_i \leq 10^{18}$, $1 \leq T \leq 50000$, $1 \leq x \leq n$, $1 \leq y \leq m$, $1 \leq z \leq 10^9$, $1 \leq \sum p \leq 10^5$. It is guaranteed that at any time $z \leq a_{x,y}$. #### Notes Translated from [AGM 2022 Qualification Round C TimeToFarm](https://judge.agm-contest.com/team/problems/10/text). Translated by ChatGPT 5