I - League of Kyoto

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

左右一列に並んだ 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_j0 または 1 である。
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq l_j \leq r_j \leq N

入力

入力は以下の形式で標準入力から与えられる。

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

出力

各クエリ処理後の合計スコアを順に出力せよ。


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