Maximize The Value

문제

You are given a one-based array consisting of $NN$ integers: $A_1,A_2,\cdots ,A_{N}A\_1,\; A\_2,\; \backslash cdots\; ,\; A\_N$. Initially, the value of each element is set to $00$.

There are $MM$ operations (numbered from $11$ to $MM$). Operation $ii$ is represented by ⟨L_i , R_i , X_i⟩. If operation $ii$ is executed, all elements $A_{j}A\_j$ for L_i ≤ j ≤ R_i will be increased by $X_{i}X\_i$.

You have to answer $QQ$ independent queries. Each query is represented by ⟨K, S, T⟩ which represents the following task. Choose a range $[l,r][l,\; r]$ satisfying S ≤ l ≤ r ≤ T, and execute operations $l,l+1,\dots ,rl,\; l\; +\; 1,\; \backslash dots\; ,\; r$. The answer to the query is the maximum value of $A_{K}A\_K$ after the operations are executed among all possible choices of $ll$ and $rr$.

입력

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

Each of the next $MM$ lines consists of three integers $L_{i}L\_i$ $R_{i}R\_i$ $X_{i}X\_i$ (1 ≤ L_i ≤ R_i ≤ N; -100\, 000 ≤ X_i ≤ 100\, 000).

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

Each of the next $QQ$ lines consists of three integers $KK$ $SS$ $TT$ (1 ≤ K ≤ N; 1 ≤ S ≤ T ≤ M).

출력

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

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