题目描述

给定一个由 $N$ 个整数构成的一维数组 $A_1, A_2, \cdots, A_N$，初始时每个元素的值均为 $0$。

有 $M$ 个操作（编号从 $1$ 到 $M$）。第 $i$ 个操作表示为 $\langle L_i, R_i, X_i \rangle$。执行第 $i$ 个操作时，所有满足 $L_i \leq j \leq R_i$ 的 $A_j$ 都会增加 $X_i$。

你需要回答 $Q$ 个独立的询问。每个询问表示为 $\langle K, S, T \rangle$，其含义如下：选择一个区间 $[l, r]$，满足 $S \leq l \leq r \leq T$，并依次执行操作 $l, l+1, \dots, r$。对于所有可能的 $l$ 和 $r$，询问的答案为执行这些操作后 $A_K$ 的最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \leq N, M \leq 100\,000$）。

接下来的 $M$ 行，每行包含三个整数 $L_i$、$R_i$、$X_i$（$1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$）。

接下来一行包含一个整数 $Q$（$1 \leq Q \leq 100\,000$）。

接下来的 $Q$ 行，每行包含三个整数 $K$、$S$、$T$（$1 \leq K \leq N; 1 \leq S \leq T \leq M$）。

输出格式

对于每个询问，输出一行，表示该询问的答案。

2 6
1 1 -50
1 2 -20
2 2 -30
1 1 60
1 2 40
2 2 10
5
1 1 6
2 1 6
1 1 3
2 1 3
1 1 2

100
50
0
0
-20

5 3
1 3 3
2 4 -2
3 5 3
6
1 1 3
2 1 3
3 1 3
3 2 3
2 2 3
2 2 2

3
3
4
3
0
-2

提示

样例输入输出 #1 说明：

对于第 $1$ 个询问，其中一种方案是执行操作 $4$ 和 $5$。

对于第 $2$ 个询问，其中一种方案是执行操作 $4$、$5$ 和 $6$。

对于第 $3$ 个询问，唯一的方案是执行操作 $3$。

对于第 $4$ 个询问，唯一的方案是执行操作 $1$。

对于第 $6$ 个询问，唯一的方案是执行操作 $2$。

由 ChatGPT 4.1 翻译