Problem Description

There are $ N $ squares arranged in a row on a field, with $ M $ enemies hiding in them.

Each enemy has a width, and the $ i $-th enemy is hiding in the squares from $ L_i $ to $ R_i $ from the left. If you have information about one or more of these squares, you gain a score of $ s_i $.

Initially, you have no information about any of the squares.

You are given $ Q $ queries in sequence. The $ j $-th query is represented by $ t_j, l_j, r_j $, where:

• If $ t_j = 0 $, you lose information about the squares from $ l_j $ to $ r_j $ from the left.
• If $ t_j = 1 $, you gain information about the squares from $ l_j $ to $ r_j $ from the left.

Calculate the total score after each query.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ L_1 $ $ R_1 $ $ s_1 $ $ L_2 $ $ R_2 $ $ s_2 $ $ : $ $ L_M $ $ R_M $ $ s_M $ $ Q $ $ t_1 $ $ l_1 $ $ r_1 $ $ t_2 $ $ l_2 $ $ r_2 $ $ : $ $ t_Q $ $ l_Q $ $ r_Q $

Output Format

Output the total score after each query in sequence.

Sample Input and Output

Sample Input #1

4 2
1 2 5
4 4 8
3
1 1 4
0 2 4
0 1 1

Sample Output #1

13
5
0

Sample Input #2

6 3
2 3 5
2 4 4
6 6 3
5
1 1 2
1 4 6
0 2 2
1 3 4
0 6 6

Sample Output #2

9
12
7
12
9

Sample Input #3

100 10
38 64 158260522
61 81 24979445
53 77 433933447
21 32 211047202
49 53 731963982
1 12 430302156
47 57 880895728
61 74 189330739
44 98 404539679
10 49 492686568
10
1 55 81
1 32 72
0 14 67
1 13 24
1 45 56
1 9 38
0 7 61
1 4 26
1 45 58
0 44 99

Sample Output #3

2091939560
3527637312
1052783310
1756517080
3527637312
3957939468
1052783310
2186819236
3957939468
1134035926

Notes/Hints

Constraints

• All input values are integers.
• $1 \leq N, M, Q \leq 10^5$
• $1 \leq s_i \leq 10^9$
• $ t_j $ is either $ 0 $ or $ 1 $.
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq l_j \leq r_j \leq N$

Sample Explanation 1

The queries proceed as follows:
- Gain information about squares from $ 1 $ to $ 4 $.
- Since you have information about square $ 1 $, you gain a score of $ 5 $.
- Since you have information about square $ 4 $, you gain a score of $ 8 $.
- The total score is $ 13 $.
- Lose information about squares from $ 2 $ to $ 4 $.
- At this point, you only have information about square $ 1 $, so the total score is $ 5 $.
- Lose information about square $ 1 $.
- You have no information about any squares, so the total score is $ 0 $.

见题面 Input 部分

见题面 Output 部分