Description

在亚得里亚海沿岸有一个小村庄。渔民们将大海划分为 $N \times M$ 的网格，第一行紧邻海岸，最后一行最远离海岸。他们追踪鱼群和其他漂浮物的移动。大海大部分区域是空的，但有 $K$ 个感兴趣的网格单元。每个单元的位置用第 $R_i$ 行和第 $C_i$ 列表示。渔民们估计在第 $i$ 个单元捕鱼的收益为 $V_i$。注意，如果该区域主要被不受欢迎的物品占据，$V_i$ 可能为零或负数。其他所有单元的价值均视为 0。

每天，当地议会会批准一个矩形捕鱼区域，包含从第 $X$ 列到第 $Y$ 列，并从海岸向海延伸 $H$ 行。为了在选定区域捕鱼，渔民们会准备一张长度恰好为 $H$ 的渔网。虽然渔网长度固定，但宽度 $W$ 可以任意选择，且不超过 $Y - X + 1$。根据他们对海域的了解，他们会在批准的捕鱼区域内选择一个位置下网，以最大化捕获量，即渔网覆盖的所有单元的价值之和。

渔民们希望每天都选择最优的捕鱼位置。请编写程序，针对接下来 $Q$ 天批准的捕鱼区域，计算他们能获得的最大收益。你可以假设每个单元的价值是恒定的，不会因前几天捕鱼而减少。

Input Format

第一行包含行数 $N$、列数 $M$ ，第二行包含非空单元数 $K$。接下来的 $K$ 行，每行包含 $R_i$、$C_i$ 和 $V_i$，用空格分隔。行号从 1 到 $N$，列号从 1 到 $M$。所有 $V_i$ 均为整数。

下一行包含查询数 $Q$。第 $j$ 个查询由三个整数 $H'_j$、$X'_j$ 和 $Y'_j$ 描述。为保证按顺序回答查询，查询以编码形式给出。实际查询可按如下方式计算：

$$\begin{aligned} H_j &= H'_j \oplus A_{j-3}, \\ X_j &= X'_j \oplus A_{j-2}, \\ Y_j &= Y'_j \oplus A_{j-1}, \end{aligned}$$

其中 $A_j$ 表示第 $j$ 个查询的答案（若 $j \leq 0$，则为 0），$\oplus$ 表示按位异或操作。你的程序应找到覆盖前 $H_j$ 行、列区间为 $X_j$ 到 $Y_j$ 的区域内，渔民能获得的最大收益。

Output Format

对于每个查询，输出一行，表示最大捕获收益。注意，渔民也可以选择不下网，此时收益为 0。

10 7
12
2 6 -5
3 3 3
4 2 -2
4 6 2
5 3 -1
5 5 5
7 1 8
7 7 4
8 4 -3
8 5 1
9 6 -4
10 3 2
6
5 1 5
10 1 0
7 1 11
15 15 6
9 1 0
3 7 1

7
13
0
6
3
0

Hint

说明

解码后的查询列表：

5 1 5
10 1 7
7 6 6
8 2 6
4 1 6
3 1 2

输入范围

• $1 \leq N, M, K, Q \leq 300\,000$
• $|V_i| \leq 1000$

由 ChatGPT 4.1 翻译