C'è un array $a$ di lunghezza $n$, dove l'$i$-esimo numero è $a_i$. Inoltre, ogni numero ha un punteggio, e il punteggio dell'$i$-esimo numero è $c_i$. Alice e Bob giocano a turno, e Alice inizia per prima.
Nel turno corrente, il giocatore copia prima l'array $a$ nell'array $b$ ed esegue un programma di mescolamento casuale per mescolare casualmente l'array $b$. Nello specifico, il programma di mescolamento casuale selezionerà una delle permutazioni di $b$ con uguale probabilità e sostituirà l'array originale $b$ con essa. Supponiamo che la lunghezza attuale dell'array $a$ sia $m$; allora il giocatore può scegliere un intero $k$ tale che $0 \le k \le m$ e $a[1 \dots k] = b[1 \dots k]$, e quindi eliminare $a[1 \dots k]$ (cioè il prefisso di lunghezza $k$ di $a$) e ottenere il punteggio dei numeri eliminati. Il gioco termina quando l'array $a$ viene svuotato.
Si noti che l'array $a$ e il suo array dei punteggi $c$ non verranno mescolati durante l'intero processo, ma verranno rimossi solo i loro prefissi.
Sia Alice che Bob vogliono massimizzare i propri punteggi. Alice vuole sapere qual è il suo punteggio atteso quando entrambi i giocatori adottano strategie ottimali.
Alice ha anche effettuato $q$ gruppi di modifiche (modificando l'array e i punteggi), e vuole che tu trovi la risposta per l'array iniziale, così come le risposte dopo ogni gruppo di modifiche.
Input
La prima riga contiene un intero $n$ ($1 \le n \le 10^6$), che rappresenta la lunghezza dell'array iniziale $a$.
La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), che rappresentano l'array iniziale $a$.
La terza riga contiene $n$ interi $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), che rappresentano il punteggio di ciascun numero nell'array.
La riga successiva contiene un intero $q$ ($0 \le q \le 10$), che rappresenta il numero di gruppi di modifiche.
Di seguito vengono descritti $q$ gruppi di modifiche:
Per ogni gruppo di modifiche, la prima riga contiene $k_i$ ($1 \le k_i \le 10^5$), che indica il numero di modifiche in questo gruppo.
Le successive $k_i$ righe contengono ciascuna tre interi $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), ad indicare che $a_{p_j}$ viene modificato in $x_j$ e $c_{p_j}$ viene modificato in $y_j$.
È garantito che $p_1 < p_2 < \dots < p_{k_i}$.
Output
Stampa un totale di $q + 1$ righe, ciascuna contenente un numero in virgola mobile che rappresenta la risposta.
La prima riga è la risposta per l'array iniziale, seguita da $q$ righe per le risposte dopo ogni gruppo di modifiche.
Una risposta è considerata corretta se l'errore relativo o assoluto rispetto alla risposta standard non supera $10^{-9}$.
Esempi
Input 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Output 1
1.333333333333 3.000000000000 4.000000000000
Input 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Output 2
9.013888888889
Note
Questo problema ha una dimensione di input elevata, si prega di utilizzare un metodo di input efficiente.