有一个长度为 $n$ 的数组 $a$，其中第 $i$ 个数为 $a_i$。此外，每个数都有一个得分，第 $i$ 个数的得分为 $c_i$。Alice 和 Bob 轮流进行游戏，Alice 先手。

在当前轮中，轮到的玩家首先将数组 $a$ 复制到数组 $b$，并运行一个随机洗牌程序来随机打乱数组 $b$。具体来说，随机洗牌程序会等概率地选择 $b$ 的排列之一，并用其替换原数组 $b$。假设当前数组 $a$ 的长度为 $m$，那么玩家可以选择一个整数 $k$，满足 $0 \le k \le m$ 且 $a[1 \dots k] = b[1 \dots k]$，然后删除 $a[1 \dots k]$（即 $a$ 的长度为 $k$ 的前缀）并获得被删除数字的得分之和。当数组 $a$ 被清空时，游戏结束。

注意，在整个过程中，数组 $a$ 及其得分数组 $c$ 本身不会被打乱，而只是它们的前缀会被移除。

Alice 和 Bob 都希望最大化自己的得分。Alice 想知道当双方都采用最优策略时，她的期望得分是多少。

Alice 还进行了 $q$ 组修改（修改数组和得分），她希望你求出初始数组的答案，以及每组修改之后的答案。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示初始数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示初始数组 $a$。

第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$)，表示数组中每个数的得分。

下一行包含一个整数 $q$ ($0 \le q \le 10$)，表示修改的组数。

接下来描述 $q$ 组修改：

对于每组修改，第一行包含一个整数 $k_i$ ($1 \le k_i \le 10^5$)，表示该组修改中的修改次数。

接下来的 $k_i$ 行，每行包含三个整数 $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$)，表示将 $a_{p_j}$ 修改为 $x_j$，并将 $c_{p_j}$ 修改为 $y_j$。

保证 $p_1 < p_2 < \dots < p_{k_i}$。

输出格式

输出共 $q + 1$ 行，每行包含一个浮点数，表示答案。

第一行是初始数组的答案，随后是 $q$ 行，分别表示每组修改之后的答案。

如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-9}$，则被视为正确。

样例

输入样例 1

2
1 2
1 1
2
1
2 1 2
1
1 1 2

输出样例 1

1.333333333333
3.000000000000
4.000000000000

输入样例 2

6
1 1 4 5 1 4
2 3 3 3 3 3
0

输出样例 2

9.013888888889

说明

本题输入数据量较大，请使用高效的输入方式。