Dana jest tablica $a$ długości $n$, gdzie $i$-tą liczbą jest $a_i$. Ponadto każda liczba ma przypisaną liczbę punktów, a liczba punktów $i$-tej liczby wynosi $c_i$. Alice i Bob wykonują ruchy na zmianę, przy czym zaczyna Alice.
W bieżącej rundzie gracz najpierw kopiuje tablicę $a$ do tablicy $b$ i uruchamia program losowo tasujący tablicę $b$. Dokładniej, program losowego tasowania wybiera z jednakowym prawdopodobieństwem jedną z permutacji tablicy $b$ i zastępuje nią oryginalną tablicę $b$. Załóżmy, że aktualna długość tablicy $a$ wynosi $m$; wówczas gracz może wybrać liczbę całkowitą $k$ taką, że $0 \le k \le m$ oraz $a[1 \dots k] = b[1 \dots k]$, a następnie usunąć $a[1 \dots k]$ (czyli prefiks tablicy $a$ o długości $k$) i zdobyć punkty usuniętych liczb. Gra kończy się, gdy tablica $a$ zostanie opróżniona.
Zauważ, że tablica $a$ oraz jej tablica punktów $c$ nie są tasowane w trakcie całego procesu, a jedynie usuwane są ich prefiksy.
Zarówno Alice, jak i Bob chcą zmaksymalizować swoje wyniki. Alice chce wiedzieć, jaki jest jej oczekiwany wynik, gdy oboje gracze stosują strategie optymalne.
Alice wykonała również $q$ grup modyfikacji (zmieniających tablicę oraz punkty) i chce, abyś znalazł odpowiedź dla tablicy początkowej, a także odpowiedzi po każdej grupie modyfikacji.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą długość początkowej tablicy $a$.
Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), opisujących początkową tablicę $a$.
Trzeci wiersz zawiera $n$ liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), oznaczających punkty poszczególnych liczb w tablicy.
Kolejny wiersz zawiera liczbę całkowitą $q$ ($0 \le q \le 10$), oznaczającą liczbę grup modyfikacji.
Poniżej opisano $q$ grup modyfikacji:
Dla każdej grupy modyfikacji pierwszy wiersz zawiera liczbę $k_i$ ($1 \le k_i \le 10^5$), oznaczającą liczbę modyfikacji w tej grupie.
Kolejne $k_i$ wierszy zawiera po trzy liczby całkowite $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), oznaczające, że $a_{p_j}$ zostaje zmienione na $x_j$, a $c_{p_j}$ zostaje zmienione na $y_j$.
Gwarantowane jest, że $p_1 < p_2 < \dots < p_{k_i}$.
Wyjście
Wypisz łącznie $q + 1$ wierszy, z których każdy zawiera liczbę zmiennoprzecinkową oznaczającą odpowiedź.
Pierwszy wiersz to odpowiedź dla tablicy początkowej, a kolejne $q$ wierszy to odpowiedzi po każdej grupie modyfikacji.
Odpowiedź uznaje się za poprawną, jeśli błąd względny lub bezwzględny w stosunku do odpowiedzi wzorcowej nie przekracza $10^{-9}$.
Przykład
Wejście 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Wyjście 1
1.333333333333 3.000000000000 4.000000000000
Wejście 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Wyjście 2
9.013888888889
Uwagi
To zadanie ma duży rozmiar danych wejściowych, prosimy o użycie szybkiej metody wczytywania danych.