给定一个长度为 $N$ 的数组，下标从 1 开始：$A_1, A_2, \dots, A_N$。初始时，每个元素的值均为 0。

共有 $M$ 个操作（编号从 1 到 $M$）。第 $i$ 个操作由 $\langle L_i, R_i, X_i \rangle$ 表示。如果执行操作 $i$，则所有满足 $L_i \le j \le R_i$ 的元素 $A_j$ 都会增加 $X_i$。

你需要回答 $Q$ 个独立的询问。每个询问由 $\langle K, S, T \rangle$ 表示，具体任务如下：选择一个满足 $S \le l \le r \le T$ 的区间 $[l, r]$，并执行操作 $l, l+1, \dots, r$。询问的答案是在所有可能的 $l$ 和 $r$ 选择中，执行操作后 $A_K$ 的最大值。

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 100\,000$)。

接下来的 $M$ 行，每行包含三个整数 $L_i, R_i, X_i$ ($1 \le L_i \le R_i \le N$; $-100\,000 \le X_i \le 100\,000$)。

下一行包含一个整数 $Q$ ($1 \le Q \le 100\,000$)。

接下来的 $Q$ 行，每行包含三个整数 $K, S, T$ ($1 \le K \le N$; $1 \le S \le T \le M$)。

输出格式

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

样例

输入 1

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

输出 1

100
50
0
0
-20

说明 1

对于询问 1，其中一种方案是执行操作 4 和 5。 对于询问 2，其中一种方案是执行操作 4、5 和 6。 对于询问 3，唯一的方案是执行操作 3。 对于询问 4，唯一的方案是执行操作 1。 对于询问 5，唯一的方案是执行操作 2。

输入 2

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

输出 2

3
3
4
3
0
-2