#215742. [ICPC 2023 Jakarta R] Maximize The Value

You are given a one-based array consisting of integers: . Initially, the value of each element is set to .

There are operations (numbered from to ). Operation is represented by . If operation is executed, all elements for will be increased by .

You have to answer independent queries. Each query is represented by which represents the following task. Choose a range satisfying , and execute operations . The answer to the query is the maximum value of after the operations are executed among all possible choices of and .

The first line consists of two integers ( ).

Each of the next lines consists of three integers ( ).

The following line consists of an integer ( ).

Each of the next lines consists of three integers ( ).

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

Explanation for the sample input/output #1

For query , one of the solutions is to execute operation and .

For query , one of the solutions is to execute operation , , and .

For query , the only solution is to execute operation .

For query , the only solution is to execute operation .

For query , the only solution is to execute operation .