Fishing

There is a small village on the coast of the Adriatic Sea. The fishermen map the sea as a grid of $N × M$ cells. The first row is adjacent to the coast, and the last row is the farthest away. They track the movement of fish and other items floating in the sea. Most of the sea is empty, but there are $K$ cells of interest. The location of the $i$-th cell is row $R_i$ and column $C_i$. The fishermen estimate that their catch from fishing in the $i$-th cell is worth $V_i$. $V_i$ can be zero or negative if that area is mostly occupied by undesired items. All other cells 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 prepare a fishing net exactly $H$ units long. The net has a fixed length, but it can be rolled out to any width $W$ up to $Y - X + 1$. Based on what they know about the sea, the fishermen drop the net somewhere within the approved area so that the sum of the cell values it covers is as large as possible.

Write a program that finds the best catch for the approved fishing areas over the next $Q$ days. Cell values stay constant. Fishing on earlier days does not deplete them.

The first line contains the number of rows $N$, the number of columns $M$, and the number of non-empty cells $K$. Each of the next $K$ lines gives the row $R_i$, column $C_i$, and value $V_i$ of one cell, separated by spaces. Rows are numbered from 1 to $N$, and columns from 1 to $M$. All $V_i$ are integers.

The next line contains the number of queries $Q$. The $j$-th query is given as three integers $A'_j$, $X'_j$, and $Y'_j$. The queries are encoded so that your program must answer them in the given order. The actual query is computed as follows.

$H_j = H'_j \oplus A_{j-3}$

$X_j = X'_j \oplus A_{j-2}$

$Y_j = Y'_j \oplus A_{j-1}$

Here $A_j$ is the answer to the $j$-th query, and $A_j$ is $0$ when $j \le 0$. $\oplus$ denotes bitwise XOR. Your program must 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 the maximum catch value on its own line. The fishermen can always keep an empty net, which has a value of $0$.

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

The decoded list of queries:

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