問題文

岩井星には岩井星人 $1,\ \dots,\ N$ が住んでいます。
また、岩井星には家 $1,\ \dots,\ M$ があり、各 $i \ (1 \leq i \leq N)$ について、岩井星人 $i$ は家 $i$ に住んでいます。

各岩井星人はプログラミング能力の高さを表すレートという数値を持っており、岩井星人 $i$ のレートは $A_i$ です。
また、岩井星人 $i$ は家 $L_i,\ L_i + 1,\ \dots,\ R_i$ に住んでいる岩井星人を同じ地元に住んでいると見なしています。

そこで、各 $j \ (1 \leq j \leq M)$ について、$B_j$ を家 $j$ に住んでいる岩井星人のレート(家 $j$ に岩井星人が住んでいない場合は $B_j = 0$ )とし、岩井星人 $i$ の地元における天才度を $\sum_{j = L_i}^{R_i} (A_i - B_j)$ で定義します。
ただし、後述するように $B_j$ および $L_i,\ R_i$ の値は更新されるので、天才度もそれに伴って更新されることに注意してください。

今から $Q$ 回のイベントが起き、 $k$ 回目のイベントでは岩井星人 $X_k$ は家 $Y_k$ に引越して、新たに、家 $U_k,\ U_k + 1,\ \dots,\ V_k$ に住んでいる岩井星人を同じ地元に住んでいると見なすようになります。このとき、$L_{X_k},\ R_{X_k}$ の値がそれぞれ $U_{k},\ V_{k}$ に更新されます。
ただし、イベント $k$ の直前において家 $Y_k$ には岩井星人が住んでいないことが保証されます。

各イベントが起こった直後の、岩井星人の天才度の総和を答えてください。

制約

• $1 \le N < M \le 2 \times 10^5$
• $0 \le A_i \le 10^8$
• $1 \le L_i \le R_i \le M$
• $1 \le Q \le 2 \times 10^5$
• $1 \le X_k \le N$
• $1 \le Y_k \le M$
• イベント $k$ の直前において家 $Y_k$ には岩井星人は住んでいない
• $1 \le U_k \le V_k \le M$
• 入力は全て整数

入力

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

$N\ M$
$A_1\ L_1\ R_1$
$A_2\ L_2\ R_2$
$\vdots$
$A_N\ L_N\ R_N$
$Q$
$X_1\ Y_1\ U_1\ V_1$
$X_2\ Y_2\ U_2\ V_2$
$\vdots$
$X_Q\ Y_Q\ U_Q\ V_Q$

出力

$Q$ 行出力せよ。
$k$ 行目にはイベント$k$が起こった直後の岩井星人の天才度の和を出力せよ。

サンプル

3 5
200 1 1
600 1 3
1000 1 4
2
3 4 3 5
1 5 4 5

3000
2200

5 10
9 1 2
1 1 3
8 2 3
1 1 5
9 4 7
3
1 8 6 8
5 6 6 6
2 5 2 5

31
5
6

2 8
10 1 3
15 4 5
2
1 5 1 3
2 1 6 8

35
60

2 200000
9 1 15
181 2 2
3
2 3 5 9
2 181181 1 200000
2 2 2 2

850
36199936
-55