長さ $n$ の配列 $a$ があり、$i$ 番目の数は $a_i$ です。さらに、各数にはスコアがあり、$i$ 番目の数のスコアは $c_i$ です。Alice と Bob が交互に手番を行い、Alice が先手です。
現在のラウンドでは、手番のプレイヤーはまず配列 $a$ を配列 $b$ にコピーし、ランダムシャッフルプログラムを実行して配列 $b$ をランダムにシャッフルします。具体的には、ランダムシャッフルプログラムは $b$ の順列のうち $1$ つを等確率で選び、元の配列 $b$ をそれで置き換えます。現在の配列 $a$ の長さを $m$ とすると、プレイヤーは $0 \le k \le m$ かつ $a[1 \dots k] = b[1 \dots k]$ を満たす整数 $k$ を選び、$a[1 \dots k]$(すなわち $a$ の長さ $k$ の接頭辞)を削除して、削除された数のスコアを得ることができます。配列 $a$ が空になった時点でゲームは終了します。
なお、全体の過程を通して配列 $a$ とそのスコア配列 $c$ 自体はシャッフルされず、それらの接頭辞のみが削除されることに注意してください。
Alice と Bob はともに自身のスコアを最大化したいと考えています。Alice は、両プレイヤーが最適な戦略をとったときの彼女の期待スコアがいくらになるかを知りたいと思っています。
また、Alice は $q$ グループの更新(配列とスコアの変更)を行いました。彼女は初期配列に対する答えと、各グループの更新後の答えを求めてほしいと思っています。
入力
最初の行には、初期配列 $a$ の長さを表す整数 $n$ ($1 \le n \le 10^6$) が含まれます。
$2$ 行目には、初期配列 $a$ を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が含まれます。
$3$ 行目には、配列内の各数のスコアを表す $n$ 個の整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$) が含まれます。
次の行には、更新のグループ数を表す整数 $q$ ($0 \le q \le 10$) が含まれます。
続いて、$q$ グループの更新が記述されます:
各更新グループについて、最初の行にはこのグループ内の更新回数を表す $k_i$ ($1 \le k_i \le 10^5$) が含まれます。
続く $k_i$ 行にはそれぞれ、$a_{p_j}$ を $x_j$ に変更し、$c_{p_j}$ を $y_j$ に変更することを表す $3$ つの整数 $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$) が含まれます。
$p_1 < p_2 < \dots < p_{k_i}$ が保証されます。
出力
合計 $q + 1$ 行を出力してください。各行には答えを表す浮動小数点数を $1$ つ出力します。
$1$ 行目は初期配列に対する答えであり、続く $q$ 行は各更新グループの後の答えです。
想定解との相対誤差または絶対誤差が $10^{-9}$ 以下であれば、正解とみなされます。
入出力例
入力 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
出力 1
1.333333333333 3.000000000000 4.000000000000
入力 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
出力 2
9.013888888889
注記
この問題は入力サイズが大きいため、高速な入力方法を使用してください。