There is an array $a$ of length $n$, where the $i$-th number is $a_i$. Additionally, each number has a score, and the score of the $i$-th number is $c_i$. Alice and Bob take turns, with Alice going first.
In the current round, the player first copies the array $a$ to array $b$ and runs a random shuffle program to randomly shuffle array $b$. Specifically, the random shuffle program will select one of the permutations of $b$ with equal probability and replace the original array $b$ with it. Suppose the current length of array $a$ is $m$, then the player can choose an integer $k$ such that $0 \le k \le m$ and $a[1 \dots k] = b[1 \dots k]$, and then delete $a[1 \dots k]$ (i.e., the prefix of length $k$ of $a$) and obtain the score of the deleted numbers. The game ends when the array $a$ is emptied.
Note that the array $a$ and its score array $c$ will not be shuffled throughout the entire process, but only their prefixes will be removed.
Both Alice and Bob want to maximize their scores. Alice wants to know what her expected score is when both players adopt optimal strategies.
Alice also made $q$ groups of modifications (modifying the array and scores), and she wants you to find the answer for the initial array, as well as the answers after each group of modifications.
Input
The first line contains an integer $n$ ($1 \le n \le 10^6$), representing the length of the initial array $a$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), representing the initial array $a$.
The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), representing the score of each number in the array.
The next line contains an integer $q$ ($0 \le q \le 10$), representing the number of modifications.
The following describes $q$ groups of modifications:
For each group of modifications, the first line contains $k_i$ ($1 \le k_i \le 10^5$), indicating the number of modifications in this group.
The next $k_i$ lines each contain three integers $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), indicating that $a_{p_j}$ is modified to $x_j$ and $c_{p_j}$ is modified to $y_j$.
It is guaranteed that $p_1 < p_2 < \dots < p_{k_i}$.
Output
Output a total of $q + 1$ lines, each line containing a floating-point number representing the answer.
The first line is the answer for the initial array, followed by $q$ lines for the answers after each group of modifications.
An answer is considered correct if the relative or absolute error compared to the standard answer does not exceed $10^{-9}$.
Examples
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
This problem has a large input size, please use an efficient input method.