Det finns en array $a$ av längd $n$, där det $i$-te talet är $a_i$. Dessutom har varje tal en poäng, och poängen för det $i$-te talet är $c_i$. Alice och Bob turas om, och Alice börjar.
I den aktuella rundan kopierar spelaren först arrayen $a$ till arrayen $b$ och kör ett slumpmässigt blandningsprogram för att slumpmässigt blanda arrayen $b$. Mer specifikt väljer blandningsprogrammet en av permutationerna av $b$ med lika sannolikhet och ersätter den ursprungliga arrayen $b$ med den. Antag att den aktuella längden på arrayen $a$ är $m$; då kan spelaren välja ett heltal $k$ sådant att $0 \le k \le m$ och $a[1 \dots k] = b[1 \dots k]$, och sedan ta bort $a[1 \dots k]$ (dvs. prefixet av längd $k$ av $a$) och få poängen för de borttagna talen. Spelet slutar när arrayen $a$ är tömd.
Observera att arrayen $a$ och dess poängarray $c$ inte blandas under hela processen, utan endast deras prefix tas bort.
Både Alice och Bob vill maximera sina poäng. Alice vill veta vad hennes förväntade poäng är när båda spelarna använder optimala strategier.
Alice gjorde också $q$ grupper av modifieringar (som ändrar arrayen och poängen), och hon vill att du hittar svaret för den ursprungliga arrayen samt svaren efter varje grupp av modifieringar.
Indata
Den första raden innehåller ett heltal $n$ ($1 \le n \le 10^6$), som representerar längden på den ursprungliga arrayen $a$.
Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerar den ursprungliga arrayen $a$.
Den tredje raden innehåller $n$ heltal $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), som representerar poängen för varje tal i arrayen.
Nästa rad innehåller ett heltal $q$ ($0 \le q \le 10$), som representerar antalet grupper av modifieringar.
Följande beskriver $q$ grupper av modifieringar:
För varje grupp av modifieringar innehåller den första raden $k_i$ ($1 \le k_i \le 10^5$), vilket anger antalet modifieringar i denna grupp.
De följande $k_i$ raderna innehåller var och en tre heltal $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), vilket anger att $a_{p_j}$ ändras till $x_j$ och $c_{p_j}$ ändras till $y_j$.
Det garanteras att $p_1 < p_2 < \dots < p_{k_i}$.
Utdata
Skriv ut totalt $q + 1$ rader, där varje rad innehåller ett flyttal som representerar svaret.
Den första raden är svaret för den ursprungliga arrayen, följt av $q$ rader för svaren efter varje grupp av modifieringar.
Ett svar betraktas som korrekt om det relativa eller absoluta felet jämfört med standardsiffran inte överstiger $10^{-9}$.
Exempel
Indata 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Utdata 1
1.333333333333 3.000000000000 4.000000000000
Indata 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Utdata 2
9.013888888889
Notering
Detta problem har en stor indatastorlek, använd gärna en effektiv inläsningsmetod.