AT_bogosortcontest_div2_m Dynamic Range Edge MST

長さ $ N-1 $ の数列 $ R = (R_1, \dots, R_{N-1}), \ W = (W_1, \dots, W_{N-1}) $ に対して、 $ N $ 頂点の重み付き無向グラフ $ G(R, W) $ を次のように定義します。 - $ N $ 個の頂点 $ 1, \dots, N $ からなる。 - 各 $ i \ (1 \leq i \leq N-1) $ および $ i + 1 \leq j \leq i + R_i $ を満たすすべての $ j $ について、頂点 $ i $ と頂点 $ j $ の間に重み $ W_i $ の無向辺がある。 はじめに、長さ $ N-1 $ の整数列 $ R, W $ が与えられます。 その後、 $ Q $ 個のクエリを順に処理してください。 各クエリは独立ではなく、変更は以降のクエリに引き継がれます。 $ j $ 番目のクエリでは $ 3 $ つの整数 $ i_j, r_j, w_j $ が与えられるので、 $ R_{i_j} $ を $ r_j $ に、 $ W_{i_j} $ を $ w_j $ に変更し、その後、 $ G(R, W) $ の最小全域木の辺の重みの総和を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ R_1 $ $ R_2 $ $ \dots $ $ R_{N-1} $ $ W_1 $ $ W_2 $ $ \dots $ $ W_{N-1} $ $ Q $ $ i_1 $ $ r_1 $ $ w_1 $ $ i_2 $ $ r_2 $ $ w_2 $ $ \vdots $ $ i_Q $ $ r_Q $ $ w_Q $

答えを合計 $ Q $ 行で出力せよ。 $ j $ 行目には、 $ j $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、頂点 $ 1 $ と $ 2 $ を結ぶ重み $ 3 $ の辺、頂点 $ 1 $ と $ 4 $ を結ぶ重み $ 3 $ の辺、頂点 $ 2 $ と $ 3 $ を結ぶ重み $ 1 $ の辺を使った部分グラフが最小全域木となるので、答えは $ 7 $ です。 $ 2 $ 番目のクエリでは、頂点 $ 1 $ と $ 2 $ を結ぶ重み $ 0 $ の辺、頂点 $ 1 $ と $ 3 $ を結ぶ重み $ 0 $ の辺、頂点 $ 3 $ と $ 4 $ を結ぶ重み $ 5 $ の辺を使った部分グラフが最小全域木となるので、答えは $ 5 $ です。 $ 3 $ 番目のクエリでは、頂点 $ 1 $ と $ 2 $ を結ぶ重み $ 0 $ の辺、頂点 $ 1 $ と $ 3 $ を結ぶ重み $ 0 $ の辺、頂点 $ 2 $ と $ 4 $ を結ぶ重み $ 1 $ の辺を使った部分グラフが最小全域木となるので、答えは $ 1 $ です。 ### Constraints - $ 2 \leq N \leq 10^5 $ - $ 1 \leq Q \leq 10^5 $ - $ 1 \leq R_i \leq \min(N - i, \textcolor{red}{5}) $ （ $ 1 \leq i \leq N-1 $ ） - $ 0 \leq W_i \leq 10^9 $ （ $ 1 \leq i \leq N-1 $ ） - $ 1 \leq i_j \leq N-1 $ （ $ 1 \leq j \leq Q $ ） - $ 1 \leq r_j \leq \min(N-i_j, \textcolor{red}{5}) $ （ $ 1 \leq j \leq Q $ ） - $ 0 \leq w_j \leq 10^9 $ （ $ 1 \leq j \leq Q $ ） - 入力はすべて整数