题目描述

There is a small village situated on the coast of the Adriatic Sea. The fishermen map the sea as a grid of $N \times M$ cells such that the first row is adjacent to the coast and the last row is the furthest away. They track the movement of fish and other items floating in the sea. The sea is mostly empty, but there are $K$ grid cells of interest. The location of each such point is denoted by row $R_i$ and column $C_i$. The fishermen estimate that their catch from fishing in the $i$-th cell is going to be worth $V_i$. Note that $V_i$ can be zero or negative if the corresponding area is predominantly occupied by undesired items. All other cells are considered to have a value of 0.

Every day, the local council approves a rectangular fishing area that includes columns from $X$ to $Y$ and extends $H$ rows from the shore into the sea. To fish in the selected area, the fishermen will prepare a fishing net that is exactly $H$ units long. Although the net has a fixed length, it can be rolled out to an arbitrary width $W$ that doesn't exceed $Y - X + 1$. Based on their information about the sea, they will drop the net somewhere within the approved fishing area to maximize the catch defined as the sum of cell values covered by the net.

The fishermen aim to choose the optimal fishing location every day. Write a program that will find the best value of their catch for the approved fishing areas for the next $Q$ days. You may assume that the cell values are constant; they are not depleted from fishing on previous days.

输入格式

The first line contains the number of rows $N$, the number of columns $M$ and the number of non-empty cells $K$. These cells are described in the following $K$ lines with their row $R_i$, column $C_i$ and value $V_i$, separated by a space. Rows are numbered from 1 to $N$ and columns from 1 to $M$. All values $V_i$ are integers.

The next line contains the number of queries $Q$. The $j$-th query is described by three integers $A'_j$, $X'_j$ and $Y'_j$. To ensure that your solution answers queries in the given order, the queries are given in an encoded form. The actual query can be computed as

$$\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} $$

where $A_j$ denotes the answer to the $j$-th query (or 0 if $j \leq 0$) and $\oplus$ denotes a bitwise xor operation. Your program should find the region with the maximum catch value that spans the first $H_j$ rows and some subrange of columns from $X_j$ to $Y_j$.

输出格式

For each query, output a single line with the maximum value of the catch. Note that the fishermen can always choose to keep an empty net with the value of 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

提示

Comment

The decoded list of queries:

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

Input limits

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