Problem Description

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$.

Input Format

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 Format

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

5 6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
5
2 1 2 3 10
2 2 5 6 15
3 4 4 5 1
1 2 5 4 13
5 1 5 6 6
4
2
5 6 1
5 4 1
3
1 3 1
2 2 1
2 3 1
1
3 3 1
2
4 6 1
1 1 1

0 3 -1 1 0

Hint

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.

Translated by ChatGPT 5