AT_kupc2018_i League of Kyoto

[problemUrl]: https://atcoder.jp/contests/kupc2018/tasks/kupc2018_i 左右一列に並んだ $ 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 $ 番目のマスの情報を得ます。 各クエリ処理後の合計スコアを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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 $ ### Sample Explanation 1 各クエリは以下のように進行します。 - 左から $ 1,\ 2,\ 3,\ 4 $ 番目のマスの情報を得ます。 - 左から $ 1 $ 番目のマスの情報を得ているので、スコア $ 5 $ を得ます。 - 左から $ 4 $ 番目のマスの情報を得ているので、スコア $ 8 $ を得ます。 - 合計スコアは $ 13 $ です。 - 左から $ 2,\ 3,\ 4 $ 番目のマスの情報を失います。 - この時点では $ 1 $ 番目のマスの情報のみ得ているので、合計スコアは $ 5 $ です。 - 左から $ 1 $ 番目のマスの情報を失います。 - どのマスの情報も得ていないので、合計スコアは $ 0 $ です。