在亚得里亚海沿岸有一个小村庄。渔民们将海域绘制成一个 $N \times M$ 的网格，其中第一行邻近海岸，最后一行距离海岸最远。他们追踪鱼类和其他漂浮在海面上的物品的移动。海域大部分是空的，但有 $K$ 个感兴趣的网格单元。每个点的位置由行 $R_i$ 和列 $C_i$ 表示。渔民估计在第 $i$ 个单元格捕鱼的收益为 $V_i$。注意，如果相应区域主要被不需要的物品占据，则 $V_i$ 可以为零或负数。所有其他单元格的价值均视为 0。

每天，当地议会都会批准一个矩形捕鱼区域，该区域包含从 $X$ 到 $Y$ 的列，并从海岸向海延伸 $H$ 行。为了在选定区域捕鱼，渔民将准备一个长度恰好为 $H$ 个单位的渔网。虽然网的长度固定，但它可以展开为不超过 $Y - X + 1$ 的任意宽度 $W$。根据他们掌握的海域信息，他们会将网投放在批准的捕鱼区域内的某个位置，以最大化捕获量，即网覆盖的单元格价值之和。

渔民们的目标是每天选择最佳的捕鱼位置。请编写一个程序，计算未来 $Q$ 天内批准的捕鱼区域的最佳捕获价值。你可以假设单元格的价值是恒定的；它们不会因为之前的捕鱼活动而耗尽。

输入格式

第一行包含行数 $N$、列数 $M$ 和非空单元格数量 $K$。接下来的 $K$ 行描述了这些单元格，每行包含其行号 $R_i$、列号 $C_i$ 和价值 $V_i$，以空格分隔。行号从 1 到 $N$，列号从 1 到 $M$。所有 $V_i$ 均为整数。

下一行包含查询次数 $Q$。第 $j$ 个查询由三个整数 $A'_j$、$X'_j$ 和 $Y'_j$ 描述。为了确保你的解决方案按给定顺序回答查询，查询以编码形式给出。实际查询可以通过以下方式计算：

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

其中 $A_j$ 表示第 $j$ 个查询的答案（如果 $j \le 0$ 则为 0），$\oplus$ 表示按位异或运算。你的程序需要找到跨越前 $H_j$ 行以及从 $X_j$ 到 $Y_j$ 的某个列子区间的最大捕获价值区域。

数据范围

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

输出格式

对于每个查询，输出一行，表示最大捕获价值。注意，渔民总是可以选择使用空网，其价值为 0。

样例

输入 1

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

输出 1

7
13
0
6
3
0

说明

解码后的查询列表：

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