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$.</p>

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

You have to answer $Q$ independent queries. Each query is represented by $⟨K, S, T⟩$ which represents the following task. Choose a range $[l, r]$ satisfying $S ≤ l ≤ r ≤ 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$.

입력 형식

The first line consists of two integers $N$ $M$ ($1 ≤ N, M ≤ 100\, 000$).</p>

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

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

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

출력 형식

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

예제 입력 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

예제 입력 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