#P17903. Random Shuffle

Random Shuffle

有长度为 nn 的数组 aa,第 ii 个元素的得分为 cic_i。Alice 先手,随后与 Bob 交替操作。

每轮操作如下。设当前剩余数组长度为 mm:

  1. 将当前 aa 复制为 bb,再等概率地选择 mm 个位置的一个排列,对 bb 进行随机打乱。每次打乱独立进行;相等元素仍按各自位置参与打乱。
  2. 当前玩家观察 bb,选择一个 0≤k≤m0\le k\le m,要求 aa 与 bb 的前 kk 个元素逐项相等。
  3. 删除 aa 的前 kk 个元素,获得这些元素的得分之和。选择 k=0k=0 时不删除元素、不获得分数,仍结束本轮。

只有复制品 bb 被打乱,aa 以及与其对应的得分始终保持原有相对顺序。剩余数组为空时游戏结束。双方都采取使自己期望总得分最大的策略,求 Alice 的期望得分。

另有 qq 组对初始数组的修改。修改累积生效。需要对修改前、以及每组修改后的数组,分别求一次从完整数组重新开始游戏的答案。

输入格式

依次输入 nn、长度为 nn 的数组 aa、长度为 nn 的数组 cc、修改组数 qq,各占一行。

每组修改先给出修改次数 kk,接着 kk 行,每行 p,x,yp,x,y 表示令 ap=x,cp=ya_p=x,c_p=y。

范围:1≤n≤1061\le n\le10^6,1≤ai,x≤n1\le a_i,x\le n,1≤ci,y≤1061\le c_i,y\le10^6,0≤q≤100\le q\le10,1≤k≤1051\le k\le10^5。同一组修改的位置满足 1≤p1<⋯<pk≤n1\le p_1<\cdots<p_k\le n。

输出格式

输出 q+1q+1 行,依次为初始状态和每组修改后的 Alice 期望得分。绝对误差或相对误差不超过 10−910^{-9} 即可。

样例 1

输入

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

输出

1.333333333333
3.000000000000
4.000000000000

样例 2

输入

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

输出

9.013888888889