题目描述

你是一个资本家，你经营着一块大小为 $n\times m$ 的方格形状的田地，第 $i$ 行第 $j$ 列上初始有 $a_{i,j}$ 数量的小麦。

在这个田地上，你圈了 $Q$ 块矩形，每块矩形表示一个农场（农场之间可能有重叠的格子）。每一个农场的小麦数量等于这个农场内每个格子的小麦的数量之和，一个农场盈利当且仅当这个农场上的小麦数量大于等于这个农场盈利所需要的小麦数 $b_i$。

不幸的是，接下来连续 $T$ 天都有强降雨，每一天都会有一些格子上的小麦数量变少。

你需要对于每个农场，确定它能盈利几天，如果 $T$ 天后仍然盈利则输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行 $m$ 个整数 $a_{i,j}$。

下一行一个整数 $Q$。接下来 $Q$ 行，每行五个数 $l,r,L,R,b$ 表示第 $i$ 个农场的左上角坐标，右下角坐标以及盈利所需的小麦数。

下一行一个整数 $T$。接下来 $T$ 段输入，每一段先输入一个 $p$ 表示这一天发生的事件，接下来 $p$ 行每一行三个整数 $x,y,z$ 表示 $(x,y)$ 格子上的小麦减少了 $z$。

输出格式

一行 $Q$ 个整数，表示答案。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $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$。保证任何时刻 $z\leq a_{x,y}$。

说明

翻译自 AGM 2022 Qualification Round C TimeToFarm。