Profitable Farm Days

You are a capitalist managing a farmland in the shape of an \(n \times m\) grid. The cell in the \(i\)-th row and \(j\)-th column initially contains \(a_{i,j}\) wheat grains.

You have partitioned the farmland into \(Q\) rectangular regions, where each rectangle represents a farm (note that the regions may overlap). The total wheat in a farm is the sum of \(a_{i,j}\) for every cell \((i,j)\) inside the rectangle. A farm is considered profitable on a day if and only if its wheat total is at least \(b_i\), the minimum requirement for profit.

Unfortunately, for the next \(T\) days heavy rains come, and on each day some cells will see their wheat count decrease by a given amount (the changes are cumulative over days).

Your task is to determine, for each farm, the number of consecutive days starting from day 1 during which it remains profitable. If a farm is still profitable after all \(T\) days have passed, output -1 for that farm.

inputFormat

The input is given as follows:

• The first line contains two integers \(n\) and \(m\) (the number of rows and columns of the grid).
• The next \(n\) lines each contain \(m\) integers. The \(j\)-th integer on the \(i\)-th line is \(a_{i,j}\), the initial wheat count in that cell.
• The following line contains an integer \(Q\), the number of farms.
• Each of the next \(Q\) lines contains five integers \(r_1, c_1, r_2, c_2, b\). The farm covers the rectangle with top-left corner at \((r_1, c_1)\) and bottom-right corner at \((r_2, c_2)\), and it is profitable if the sum of wheat in that rectangle is at least \(b\).
• The next line contains an integer \(T\), the number of days with heavy rain.
• Then for each day, the first line contains an integer \(k\), the number of update operations for that day. Each of the next \(k\) lines contains three integers \(i, j, d\), meaning that the cell at \((i, j)\) has its wheat count decreased by \(d\) on that day. Note that indices are 1-indexed and the updates accumulate over days.

outputFormat

Output \(Q\) lines. The \(i\)-th line should contain a single integer representing the number of consecutive days (starting from day 1) during which the \(i\)-th farm remains profitable. If the farm is still profitable after all \(T\) days, output -1.

sample

3 3
5 5 5
5 5 5
5 5 5
2
1 1 2 2 40
2 2 3 3 30
3
2
1 1 1
2 2 2
1
3 3 3
1
1 2 2

0
2