Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

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.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.