On taulukko $a$, jonka pituus on $n$ ja jonka $i$:s luku on $a_i$. Lisäksi jokaisella luvulla on pistemäärä, ja $i$:nnen luvun pistemäärä on $c_i$. Alice ja Bob pelaavat vuorotellen, ja Alice aloittaa.
Nykyisellä kierroksella pelaaja kopioi ensin taulukon $a$ taulukkoon $b$ ja ajaa satunnaisen sekoitusohjelman sekoittaakseen taulukon $b$ satunnaisesti. Tarkemmin sanottuna sekoitusohjelma valitsee yhden taulukon $b$ permutaatioista yhtä suurella todennäköisyydellä ja korvaa alkuperäisen taulukon $b$ sillä. Oletetaan, että taulukon $a$ nykyinen pituus on $m$; tällöin pelaaja voi valita kokonaisluvun $k$ siten, että $0 \le k \le m$ ja $a[1 \dots k] = b[1 \dots k]$, ja poistaa sitten osuuden $a[1 \dots k]$ (eli taulukon $a$ pituutta $k$ olevan etuliitteen) ja saada poistettujen lukujen pisteet. Peli päättyy, kun taulukko $a$ on tyhjennetty.
Huomaa, että taulukkoa $a$ ja sen pistetaulukkoa $c$ ei sekoiteta koko prosessin aikana, vaan ainoastaan niiden etuliitteitä poistetaan.
Sekä Alice että Bob haluavat maksimoida omat pisteensä. Alice haluaa tietää, mikä on hänen odotettu pistemääränsä, kun molemmat pelaajat käyttävät optimaalisia strategioita.
Alice teki myös $q$ muutosten ryhmää (muuttaen taulukkoa ja pisteitä), ja hän haluaa sinun etsivän vastauksen alkuperäiselle taulukolle sekä vastaukset jokaisen muutosryhmän jälkeen.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 10^6$), joka kuvaa alkuperäisen taulukon $a$ pituutta.
Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), jotka kuvaavat alkuperäisen taulukon $a$.
Kolmas rivi sisältää $n$ kokonaislukua $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), jotka kuvaavat taulukon kunkin luvun pistemäärän.
Seuraava rivi sisältää kokonaisluvun $q$ ($0 \le q \le 10$), joka kuvaa muutosryhmien lukumäärää.
Seuraavassa kuvataan $q$ muutosryhmää:
Jokaiselle muutosryhmälle ensimmäinen rivi sisältää luvun $k_i$ ($1 \le k_i \le 10^5$), joka kertoo muutosten lukumäärän tässä ryhmässä.
Seuraavat $k_i$ riviä sisältävät kukin kolme kokonaislukua $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), jotka kertovat, että $a_{p_j}$ muutetaan arvoksi $x_j$ ja $c_{p_j}$ muutetaan arvoksi $y_j$.
Taataan, että $p_1 < p_2 < \dots < p_{k_i}$.
Tuloste
Tulosta yhteensä $q + 1$ riviä, joista jokainen sisältää vastausta kuvaavan liukuluvun.
Ensimmäinen rivi on vastaus alkuperäiselle taulukolle, ja sitä seuraavat $q$ riviä ovat vastaukset kunkin muutosryhmän jälkeen.
Vastaus katsotaan oikeaksi, jos suhteellinen tai absoluuttinen virhe mallivastaukseen verrattuna on enintään $10^{-9}$.
Esimerkit
Syöte 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Tuloste 1
1.333333333333 3.000000000000 4.000000000000
Syöte 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Tuloste 2
9.013888888889
Huomautus
Tässä tehtävässä on suuri syötekoko; käytäthän tehokasta syötteenlukumenetelmää.