Untitled

#include <iostream>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;

const int N = 5e4 + 66;
const int M = 502;

ll p[M][M];
int a[M][M];
ll f[M][M];

void upd(int i, int j, ll v) {
	while (i < M) {
		int q = j;
		while (q < M) {
			f[i][q] += v;
			q |= q + 1;
		}
		i |= i + 1;
	}
}

ll get(int i, int j) {
	ll v = 0;
	while (i >= 0) {
		int q = j;
		while (q >= 0) {
			v += f[i][q];
			q &= q + 1, --q;
		}
		i &= i + 1, --i;
	}
	return v;
}

ll get(int i, int j, int x, int y) {
	return p[x][y] - p[x][j - 1] - p[i - 1][y] + p[i - 1][j - 1] + get(x, y) - get(x, j - 1) - get(i - 1, y) + get(i - 1, j - 1);
}

int L[N], R[N], qx1[N], qy1[N], qx2[N], qy2[N];
ll qmin[N];
vector<pair<pair<int,int>,int>>wupd[N];
vector<int>ask[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
			cin >> a[i][j];
			p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
		}
	}
	int Q;
	cin >> Q;
	for (int i = 1 ; i <= Q ; ++ i) {
		cin >> qx1[i] >> qy1[i] >> qx2[i] >> qy2[i] >> qmin[i];
	}
	int T;
	cin >> T;
	for (int i = 1 ; i <= T ; ++ i) {
		int nr;
		cin >> nr;
		wupd[i].resize(nr);
		for (int j = 0 ; j < nr ; ++ j) {
			cin >> wupd[i][j].first.first;
			cin >> wupd[i][j].first.second;
			cin >> wupd[i][j].second;
		}
	}
	for (int i = 1 ; i <= Q ; ++ i) {
		L[i] = 0;
		R[i] = T;
	}
	for (int rep = 0 ; rep < 4 ; ++ rep) {
		for (int i = 1 ; i <= T ; ++ i) {
			ask[i].clear();
		}
		for (int i = 1 ; i <= Q ; ++ i) {
			if (L[i] < R[i]) {
				int M = (L[i] + R[i] + 1) >> 1;
				ask[M].emplace_back(i);
			}
		}
		for (int i = 0 ; i < M ; ++ i) {
			for (int j = 0 ; j < M ; ++ j) {
				f[i][j] = 0;
			}
		}
		for (int i = 1 ; i <= T ; ++ i) {
			for (auto c : wupd[i]) {
				int x = c.first.first, y = c.first.second, val = c.second;
				upd(x, y, -val);
			}
			for (int j : ask[i]) {
				ll cur = get(qx1[j], qy1[j], qx2[j], qy2[j]);
				if (qmin[j] <= cur) {
					L[j] = i;
				} else {
					R[j] = i - 1;
				}
			}
		}
	}
	for (int i = 1 ; i <= Q ; ++ i) {
		if (L[i] == T) L[i] = -1;
		cout << L[i] << " ";
	}
}