Det er en tabell $a$ med lengde $n$, der det $i$-te tallet er $a_i$. I tillegg har hvert tall en poengsum, og poengsummen til det $i$-te tallet er $c_i$. Alice og Bob bytter på å trekke, og Alice begynner.
I den gjeldende runden kopierer spilleren først tabellen $a$ til tabellen $b$ og kjører et tilfeldig stokkeprogram for å stokke tabellen $b$ tilfeldig. Mer spesifikt vil stokkeprogrammet velge en av permutasjonene av $b$ med lik sannsynlighet og erstatte den opprinnelige tabellen $b$ med den. Anta at den nåværende lengden på tabellen $a$ er $m$; da kan spilleren velge et heltall $k$ slik at $0 \le k \le m$ og $a[1 \dots k] = b[1 \dots k]$, og deretter slette $a[1 \dots k]$ (dvs. prefikset med lengde $k$ av $a$) og få poengsummen til de slettede tallene. Spillet slutter når tabellen $a$ er tømt.
Merk at tabellen $a$ og poengtabellen $c$ ikke blir stokket gjennom hele prosessen, men at kun prefiksene deres fjernes.
Både Alice og Bob ønsker å maksimere poengsummen sin. Alice vil vite hva hennes forventede poengsum er når begge spillerne bruker optimale strategier.
Alice gjorde også $q$ grupper av endringer (endret tabellen og poengsummene), og hun vil at du skal finne svaret for den opprinnelige tabellen, samt svarene etter hver gruppe av endringer.
Inndata
Den første linjen inneholder et heltall $n$ ($1 \le n \le 10^6$), som representerer lengden på den opprinnelige tabellen $a$.
Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerer den opprinnelige tabellen $a$.
Den tredje linjen inneholder $n$ heltall $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), som representerer poengsummen til hvert tall i tabellen.
Den neste linjen inneholder et heltall $q$ ($0 \le q \le 10$), som representerer antall endringsgrupper.
Det følgende beskriver $q$ grupper av endringer:
For hver gruppe av endringer inneholder den første linjen $k_i$ ($1 \le k_i \le 10^5$), som angir antall endringer i denne gruppen.
De neste $k_i$ linjene inneholder hver tre heltall $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), som angir at $a_{p_j}$ endres til $x_j$ og $c_{p_j}$ endres til $y_j$.
Det er garantert at $p_1 < p_2 < \dots < p_{k_i}$.
Utdata
Skriv ut totalt $q + 1$ linjer, der hver linje inneholder et flyttall som representerer svaret.
Den første linjen er svaret for den opprinnelige tabellen, etterfulgt av $q$ linjer for svarene etter hver gruppe av endringer.
Et svar regnes som riktig hvis den relative eller absolutte feilen sammenlignet med fasitsvaret ikke overstiger $10^{-9}$.
Eksempler
Inndata 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Utdata 1
1.333333333333 3.000000000000 4.000000000000
Inndata 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Utdata 2
9.013888888889
Merk
Denne oppgaven har stor inndatastørrelse; vennligst bruk en effektiv innlesingsmetode.