409508: GYM103604 C TimeToFarm

You decided to enter in the farming industry. So, you bought some farms to grow wheat on them. Because you are an entrepreneur, you want to be as profitable as possible.

The terrain of the farms is given as a matrix $$$A$$$ of size $$$N x M$$$, where on each cell of the matrix there is a non-negative quantity of wheat.

You administrate $$$Q$$$ farms of rectangular shape inside the matrix $$$A$$$.

The quantity of wheat of a farm is equal to the sum of values of the cells of $$$A$$$ that are inside the farm's rectangle.

For each farm you know the minimum quantity of wheat it needs in order to be profitable.

In the next $$$T$$$ days bad weather is announced. Thus, each day the quantity of wheat of some cells is decreasing.

Your task is to determine, for each farm, the total number of days it is profitable. If a farm is profitable an infinitely number of days, you should print $$$-1$$$.

A farm is profitable on day $$$i$$$ if, after all the updates until the day $$$i$$$ (including the updates on day $$$i$$$) caused by the bad weather, the quantity of wheat of the farm is greater or equal to the minimum quantity of wheat it needs in order to be profitable.

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 500$$$), denoting the number of lines, respectively, the number of columns of the matrix $$$A$$$.

Then $$$N$$$ lines follow. Each line contains $$$M$$$ positive integers, denoting the values of the matrix $$$A$$$ ($$$0 \leq A_{i,j} \leq 10^9$$$).

The next line contains the integer $$$Q$$$ ($$$1 \leq Q \leq 50000$$$), denoting the number of farms you administrate.

Then $$$Q$$$ lines follow. Each line contains $$$5$$$ integers $$$X_1$$$, $$$Y_1$$$, $$$X_2$$$, $$$Y_2$$$, $$$MIN$$$ ($$$1 \leq X_1 \leq X_2 \leq N, 1 \leq Y_1 \leq Y_2 \leq M, 0 \leq MIN \leq 10^{18})$$$. The pair $$$(X_1, Y_1)$$$ denotes the upper-left corner of the farm, $$$(X_2, Y_2)$$$ denotes the lower-right corner of the farm, and the value $$$MIN$$$ denotes the minimum quantity of wheat the farm needs in order to be profitable.

The next line contains the integer $$$T$$$ ($$$1 \leq T \leq 50000$$$), denoting the number of days in which the value of some of the cells of the matrix $$$A$$$ is decreasing.

Then, the information for each day:

On the first line an integer $$$nr$$$, the number of updates of this day.

Then, $$$nr$$$ lines follow, each line contains $$$3$$$ integers, $$$x$$$, $$$y$$$ and $$$val$$$ ($$$1 \leq x \leq N, 1 \leq y \leq M, 1 \leq val \leq 10^9$$$), denoting that the value of the cell $$$(x, y)$$$ of the matrix $$$A$$$ is decreasing by $$$val$$$ (a pair $$$(x, y)$$$ can appear multiple times in the same day).

The total number of updates during the $$$T$$$ days is less or equal to $$$10^5$$$.

The value of a cell of matrix $$$A$$$ is always non-negative.

Note the unusual memory limit.

On a single line, print $$$Q$$$ integers, the answer for each farm in the order they appear in the input (the maximum number of days the farm is profitable, or $$$-1$$$ if it is profitable an infinitely number of days).

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