問題文

左右一列に並んだ N 個のマスで表現されるフィールド上に M 体の敵が潜んでいます。

敵は幅を持っており、i 番目の敵は左から L_i, L_i+1, ..., R_i 番目のマスに潜んでいます。 これらのマスのうち 1 マス以上の情報を得ていると、スコア s_i を得ます。

はじめ、どのマスの情報も得ていません。

Q 個のクエリが順に与えられます。 j 番目のクエリは、t_j, l_j, r_j で表され、

• t_j = 0 のとき、左から l_j, l_j+1, ..., r_j 番目のマスの情報を失います。
• t_j = 1 のとき、左から l_j, l_j+1, ..., r_j 番目のマスの情報を得ます。

各クエリ処理後の合計スコアを求めてください。

制約

• 入力は全て整数である。
• 1 \leq N, M, Q \leq 10^5
• 1 \leq s_i \leq 10^9
• t_j は 0 または 1 である。
• 1 \leq L_i \leq R_i \leq N
• 1 \leq l_j \leq r_j \leq N

入力例 1

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

出力例 1

13
5
0

各クエリは以下のように進行します。

• 左から 1, 2, 3, 4 番目のマスの情報を得ます。
  • 左から 1 番目のマスの情報を得ているので、スコア 5 を得ます。
  • 左から 4 番目のマスの情報を得ているので、スコア 8 を得ます。
  • 合計スコアは 13 です。
• 左から 2, 3, 4 番目のマスの情報を失います。
  • この時点では 1 番目のマスの情報のみ得ているので、合計スコアは 5 です。
• 左から 1 番目のマスの情報を失います。
  • どのマスの情報も得ていないので、合計スコアは 0 です。

入力例 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

出力例 2

9
12
7
12
9

入力例 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

出力例 3

2091939560
3527637312
1052783310
1756517080
3527637312
3957939468
1052783310
2186819236
3957939468
1134035926