有一個長度為 $n$ 的陣列 $a$,其中第 $i$ 個數為 $a_i$。此外,每個數都有一個得分,第 $i$ 個數的得分為 $c_i$。Alice 和 Bob 輪流進行遊戲,Alice 先手。
在當前輪中,玩家首先將陣列 $a$ 複製到陣列 $b$,並執行一個隨機洗牌程式來隨機打亂陣列 $b$。具體來說,隨機洗牌程式會以相等機率選擇 $b$ 的排列之一,並用其替換原陣列 $b$。假設當前陣列 $a$ 的長度為 $m$,那麼玩家可以選擇一個整數 $k$,滿足 $0 \le k \le m$ 且 $a[1 \dots k] = b[1 \dots k]$,然後刪除 $a[1 \dots k]$(即 $a$ 的長度為 $k$ 的前綴)並獲得被刪除數字的得分。當陣列 $a$ 被清空時,遊戲結束。
注意,在整個過程中,陣列 $a$ 及其得分陣列 $c$ 不會被打亂,而只是它們的前綴會被移除。
Alice 和 Bob 都希望最大化自己的得分。Alice 想知道當雙方都採取最佳策略時,她的期望得分是多少。
Alice 還進行了 $q$ 組修改(修改陣列和得分),她希望你求出初始陣列的答案,以及每組修改之後的答案。
輸入格式
第一行包含一個整數 $n$($1 \le n \le 10^6$),表示初始陣列 $a$ 的長度。
第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$($1 \le a_i \le n$),表示初始陣列 $a$。
第三行包含 $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$ 行,每行包含三個整數 $p_j, x_j, y_j$($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$),表示將 $a_{p_j}$ 修改為 $x_j$,並將 $c_{p_j}$ 修改為 $y_j$。
保證 $p_1 < p_2 < \dots < p_{k_i}$。
輸出格式
輸出共 $q + 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
說明
本題輸入資料量較大,請使用高效的輸入方式。