낚시

해안 근처에 작은 마을이 있다. 어부들은 바다를 $N × M$ 격자로 나누어 지도를 만든다. 첫 번째 행이 해안에 가장 가깝고, 마지막 행이 가장 멀다. 어부들은 바다에 떠다니는 물고기와 다른 물체의 움직임을 추적한다. 바다 대부분은 비어 있지만 관심 칸이 $K$개 있다. $i$번째 칸의 위치는 행 $R_i$, 열 $C_i$이다. 어부들은 $i$번째 칸에서 낚시를 하면 얻는 어획량이 $V_i$라고 추정한다. 그 구역에 원하지 않는 물체가 주로 떠 있으면 $V_i$는 0이거나 음수일 수 있다. 나머지 칸의 값은 모두 0이다.

지방 의회는 매일 열 $X$부터 $Y$까지를 포함하고 해안에서 바다 쪽으로 $H$행 뻗은 직사각형 낚시 구역을 승인한다. 어부들은 승인된 구역에서 낚시하려고 길이가 정확히 $H$인 그물을 준비한다. 그물 길이는 고정되어 있지만, 폭 $W$는 $Y - X + 1$을 넘지 않는 범위에서 자유롭게 펼 수 있다. 어부들은 바다에 대한 정보를 바탕으로 승인된 구역 안에서 그물을 놓을 위치를 고르고, 그물이 덮는 칸 값의 합이 최대가 되게 한다.

다음 $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$이면 $A_j$는 0이다. $\oplus$는 비트 XOR 연산이다. 프로그램은 처음 $H_j$행에 걸쳐 있고 열 $X_j$부터 $Y_j$ 사이의 일부 구간을 포함하는 구역 중에서 최대 어획량을 찾아야 한다.

각 질의마다 최대 어획량을 한 줄에 출력한다. 어부는 그물을 비워 두어 값 0을 택할 수도 있다.

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

디코딩된 질의 목록:

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