310897: CF1906F. Maximize The Value

F. Maximize The Valuetime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a one-based array consisting of $N$ integers: $A_1, A_2, \cdots, A_N$. Initially, the value of each element is set to $0$.

There are $M$ operations (numbered from $1$ to $M$). Operation $i$ is represented by $\langle L_i, R_i, X_i \rangle$. If operation $i$ is executed, all elements $A_j$ for $L_i \leq j \leq R_i$ will be increased by $X_i$.

You have to answer $Q$ independent queries. Each query is represented by $\langle K, S, T \rangle$ which represents the following task. Choose a range $[l, r]$ satisfying $S \leq l \leq r \leq T$, and execute operations $l, l + 1, \dots, r$. The answer to the query is the maximum value of $A_K$ after the operations are executed among all possible choices of $l$ and $r$.

Input

The first line consists of two integers $N$ $M$ ($1 \leq N, M \leq 100\,000$).

Each of the next $M$ lines consists of three integers $L_i$ $R_i$ $X_i$ ($1 \leq L_i \leq R_i \leq N; -100\,000 \leq X_i \leq 100\,000$).

The following line consists of an integer $Q$ ($1 \leq Q \leq 100\,000$).

Each of the next $Q$ lines consists of three integers $K$ $S$ $T$ ($1 \leq K \leq N; 1 \leq S \leq T \leq M$).

Output

For each query, output in a single line, an integer which represent the answer of the query.

ExamplesInput

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

Output

100
50
0
0
-20

Input

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

Output

3
3
4
3
0
-2

Note

Explanation for the sample input/output #1

For query $1$, one of the solutions is to execute operation $4$ and $5$.

For query $2$, one of the solutions is to execute operation $4$, $5$, and $6$.

For query $3$, the only solution is to execute operation $3$.

For query $4$, the only solution is to execute operation $1$.

For query $6$, the only solution is to execute operation $2$.

题目大意：
给定一个基数为1的数组，包含N个整数：A_1, A_2, ..., A_N。最初，每个元素的值设置为0。有M个操作（编号从1到M）。操作i表示为⟨L_i, R_i, X_i⟩。如果执行操作i，所有元素A_j对于L_i≤j≤R_i都将增加X_i。您必须回答Q个独立查询。每个查询由⟨K, S, T⟩表示，代表以下任务。选择一个范围[l, r]满足S≤l≤r≤T，并执行操作l, l+1, ..., r。查询的答案是执行操作后A_K的最大值，在所有可能的l和r选择中。

输入输出数据格式：
输入：
第一行包含两个整数N M（1≤N, M≤100,000）。
接下来的M行，每行包含三个整数L_i R_i X_i（1≤L_i≤R_i≤N; -100,000≤X_i≤100,000）。
接下来的一行包含一个整数Q（1≤Q≤100,000）。
接下来的Q行，每行包含三个整数K S T（1≤K≤N; 1≤S≤T≤M）。

输出：
对于每个查询，在一行中输出一个整数，表示查询的答案。题目大意： 给定一个基数为1的数组，包含N个整数：A_1, A_2, ..., A_N。最初，每个元素的值设置为0。有M个操作（编号从1到M）。操作i表示为⟨L_i, R_i, X_i⟩。如果执行操作i，所有元素A_j对于L_i≤j≤R_i都将增加X_i。您必须回答Q个独立查询。每个查询由⟨K, S, T⟩表示，代表以下任务。选择一个范围[l, r]满足S≤l≤r≤T，并执行操作l, l+1, ..., r。查询的答案是执行操作后A_K的最大值，在所有可能的l和r选择中。 输入输出数据格式： 输入： 第一行包含两个整数N M（1≤N, M≤100,000）。 接下来的M行，每行包含三个整数L_i R_i X_i（1≤L_i≤R_i≤N; -100,000≤X_i≤100,000）。 接下来的一行包含一个整数Q（1≤Q≤100,000）。 接下来的Q行，每行包含三个整数K S T（1≤K≤N; 1≤S≤T≤M）。 输出： 对于每个查询，在一行中输出一个整数，表示查询的答案。