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\).
Output
For each query, output in a single line, an integer which represent the answer of the query.
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
|
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
|
|
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
|
3
3
4
3
0
-2
|