길이가 $n$인 배열 $a$가 있으며, $i$번째 수는 $a_i$입니다. 또한 각 수에는 점수가 있으며, $i$번째 수의 점수는 $c_i$입니다. Alice와 Bob은 번갈아 가며 턴을 진행하고, Alice가 먼저 시작합니다.
현재 라운드에서 플레이어는 먼저 배열 $a$를 배열 $b$에 복사한 다음, 랜덤 셔플 프로그램을 실행하여 배열 $b$를 무작위로 섞습니다. 구체적으로, 랜덤 셔플 프로그램은 $b$의 순열 중 하나를 동일한 확률로 선택하여 원래 배열 $b$를 그것으로 대체합니다. 현재 배열 $a$의 길이를 $m$이라고 할 때, 플레이어는 $0 \le k \le m$이고 $a[1 \dots k] = b[1 \dots k]$를 만족하는 정수 $k$를 선택한 다음, $a[1 \dots k]$(즉, $a$의 길이가 $k$인 접두사)를 삭제하고 삭제된 수들의 점수를 얻을 수 있습니다. 배열 $a$가 비워지면 게임이 종료됩니다.
전체 과정 동안 배열 $a$와 그 점수 배열 $c$ 자체는 섞이지 않으며, 오직 그 접두사만 제거된다는 점에 유의하세요.
Alice와 Bob은 모두 자신의 점수를 최대화하고 싶어 합니다. Alice는 두 플레이어가 모두 최적의 전략을 채택했을 때 자신의 기댓값 점수가 얼마인지 알고 싶어 합니다.
Alice는 또한 $q$개의 수정 그룹(배열과 점수를 수정함)을 수행했으며, 초기 배열에 대한 답과 각 수정 그룹 이후의 답을 모두 구하기를 원합니다.
입력
첫 번째 줄에는 초기 배열 $a$의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.
두 번째 줄에는 초기 배열 $a$를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어집니다.
세 번째 줄에는 배열의 각 수의 점수를 나타내는 $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$개의 줄에는 각각 $a_{p_j}$를 $x_j$로 수정하고 $c_{p_j}$를 $y_j$로 수정함을 나타내는 세 정수 $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$)가 주어집니다.
$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
참고
이 문제는 입력 크기가 크므로 빠른 입출력 방법을 사용하시기 바랍니다.