Il y a un tableau $a$ de longueur $n$, où le $i$-ème nombre est $a_i$. De plus, chaque nombre a un score, et le score du $i$-ème nombre est $c_i$. Alice et Bob jouent à tour de rôle, Alice commençant en premier.
Au tour actuel, le joueur copie d'abord le tableau $a$ dans le tableau $b$ et exécute un programme de mélange aléatoire pour mélanger aléatoirement le tableau $b$. Plus précisément, le programme de mélange aléatoire sélectionne l'une des permutations de $b$ de manière équiprobable et remplace le tableau $b$ d'origine par celle-ci. Supposons que la longueur actuelle du tableau $a$ soit $m$ ; le joueur peut alors choisir un entier $k$ tel que $0 \le k \le m$ et $a[1 \dots k] = b[1 \dots k]$, puis supprimer $a[1 \dots k]$ (c'est-à-dire le préfixe de longueur $k$ de $a$) et obtenir le score des nombres supprimés. Le jeu se termine lorsque le tableau $a$ est vide.
Notez que le tableau $a$ et son tableau de scores $c$ ne seront pas mélangés tout au long du processus, seuls leurs préfixes seront supprimés.
Alice et Bob veulent tous deux maximiser leur score. Alice veut savoir quelle est son espérance de score lorsque les deux joueurs adoptent des stratégies optimales.
Alice a également effectué $q$ groupes de modifications (modifiant le tableau et les scores), et elle souhaite que vous trouviez la réponse pour le tableau initial, ainsi que les réponses après chaque groupe de modifications.
Entrée
La première ligne contient un entier $n$ ($1 \le n \le 10^6$), représentant la longueur du tableau initial $a$.
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), représentant le tableau initial $a$.
La troisième ligne contient $n$ entiers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), représentant le score de chaque nombre dans le tableau.
La ligne suivante contient un entier $q$ ($0 \le q \le 10$), représentant le nombre de groupes de modifications.
Ce qui suit décrit les $q$ groupes de modifications :
Pour chaque groupe de modifications, la première ligne contient $k_i$ ($1 \le k_i \le 10^5$), indiquant le nombre de modifications dans ce groupe.
Les $k_i$ lignes suivantes contiennent chacune trois entiers $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), indiquant que $a_{p_j}$ est modifié en $x_j$ et $c_{p_j}$ est modifié en $y_j$.
Il est garanti que $p_1 < p_2 < \dots < p_{k_i}$.
Sortie
Affichez un total de $q + 1$ lignes, chaque ligne contenant un nombre à virgule flottante représentant la réponse.
La première ligne est la réponse pour le tableau initial, suivie de $q$ lignes pour les réponses après chaque groupe de modifications.
Une réponse est considérée comme correcte si l'erreur relative ou absolue par rapport à la réponse de référence ne dépasse pas $10^{-9}$.
Exemples
Entrée 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Sortie 1
1.333333333333 3.000000000000 4.000000000000
Entrée 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Sortie 2
9.013888888889
Remarque
Ce problème a une grande taille d'entrée, veuillez utiliser une méthode de lecture rapide.