Hay un arreglo $a$ de longitud $n$, donde el $i$-ésimo número es $a_i$. Además, cada número tiene una puntuación, y la puntuación del $i$-ésimo número es $c_i$. Alice y Bob toman turnos, comenzando Alice primero.
En la ronda actual, el jugador primero copia el arreglo $a$ en el arreglo $b$ y ejecuta un programa de mezcla aleatoria para barajar aleatoriamente el arreglo $b$. Específicamente, el programa de mezcla aleatoria seleccionará una de las permutaciones de $b$ con igual probabilidad y reemplazará el arreglo original $b$ con ella. Supongamos que la longitud actual del arreglo $a$ es $m$; entonces el jugador puede elegir un entero $k$ tal que $0 \le k \le m$ y $a[1 \dots k] = b[1 \dots k]$, y luego eliminar $a[1 \dots k]$ (es decir, el prefijo de longitud $k$ de $a$) y obtener la puntuación de los números eliminados. El juego termina cuando el arreglo $a$ queda vacío.
Observa que el arreglo $a$ y su arreglo de puntuaciones $c$ no se barajarán durante todo el proceso, sino que únicamente se eliminarán sus prefijos.
Tanto Alice como Bob quieren maximizar sus puntuaciones. Alice quiere saber cuál es su puntuación esperada cuando ambos jugadores adoptan estrategias óptimas.
Alice también realizó $q$ grupos de modificaciones (modificando el arreglo y las puntuaciones), y quiere que encuentres la respuesta para el arreglo inicial, así como las respuestas después de cada grupo de modificaciones.
Entrada
La primera línea contiene un entero $n$ ($1 \le n \le 10^6$), que representa la longitud del arreglo inicial $a$.
La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), que representan el arreglo inicial $a$.
La tercera línea contiene $n$ enteros $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), que representan la puntuación de cada número en el arreglo.
La siguiente línea contiene un entero $q$ ($0 \le q \le 10$), que representa el número de grupos de modificaciones.
A continuación se describen los $q$ grupos de modificaciones:
Para cada grupo de modificaciones, la primera línea contiene $k_i$ ($1 \le k_i \le 10^5$), que indica el número de modificaciones en este grupo.
Las siguientes $k_i$ líneas contienen cada una tres enteros $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), indicando que $a_{p_j}$ se modifica a $x_j$ y $c_{p_j}$ se modifica a $y_j$.
Se garantiza que $p_1 < p_2 < \dots < p_{k_i}$.
Salida
Imprime un total de $q + 1$ líneas, cada línea con un número en punto flotante que representa la respuesta.
La primera línea es la respuesta para el arreglo inicial, seguida de $q$ líneas con las respuestas después de cada grupo de modificaciones.
Una respuesta se considera correcta si el error relativo o absoluto en comparación con la respuesta estándar no excede $10^{-9}$.
Ejemplos
Entrada 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Salida 1
1.333333333333 3.000000000000 4.000000000000
Entrada 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Salida 2
9.013888888889
Nota
Este problema tiene un tamaño de entrada grande; por favor utiliza un método de entrada eficiente.