有一個長度為 $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
說明
本題嘅輸入規模較大,請使用高效嘅輸入方法。