Có một mảng $a$ độ dài $n$, trong đó số thứ $i$ là $a_i$. Ngoài ra, mỗi số có một điểm số, và điểm số của số thứ $i$ là $c_i$. Alice và Bob lần lượt chơi, với Alice đi trước.
Ở lượt hiện tại, người chơi trước tiên sao chép mảng $a$ sang mảng $b$ và chạy một chương trình xáo trộn ngẫu nhiên để xáo trộn ngẫu nhiên mảng $b$. Cụ thể, chương trình xáo trộn ngẫu nhiên sẽ chọn một trong các hoán vị của $b$ với xác suất bằng nhau và thay thế mảng $b$ ban đầu bằng hoán vị đó. Giả sử độ dài hiện tại của mảng $a$ là $m$, khi đó người chơi có thể chọn một số nguyên $k$ sao cho $0 \le k \le m$ và $a[1 \dots k] = b[1 \dots k]$, sau đó xóa $a[1 \dots k]$ (tức là tiền tố độ dài $k$ của $a$) và nhận được điểm số của các số bị xóa. Trò chơi kết thúc khi mảng $a$ trở nên rỗng.
Lưu ý rằng mảng $a$ và mảng điểm số $c$ của nó sẽ không bị xáo trộn trong suốt toàn bộ quá trình, mà chỉ có các tiền tố của chúng bị loại bỏ.
Cả Alice và Bob đều muốn tối đa hóa điểm số của mình. Alice muốn biết điểm số kỳ vọng của cô ấy là bao nhiêu khi cả hai người chơi đều áp dụng chiến lược tối ưu.
Alice cũng đã thực hiện $q$ nhóm chỉnh sửa (chỉnh sửa mảng và điểm số), và cô ấy muốn bạn tìm đáp án cho mảng ban đầu, cũng như đáp án sau mỗi nhóm chỉnh sửa.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$), biểu thị độ dài của mảng $a$ ban đầu.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), biểu thị mảng $a$ ban đầu.
Dòng thứ ba chứa $n$ số nguyên $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), biểu thị điểm số của mỗi số trong mảng.
Dòng tiếp theo chứa một số nguyên $q$ ($0 \le q \le 10$), biểu thị số nhóm chỉnh sửa.
Phần tiếp theo mô tả $q$ nhóm chỉnh sửa:
Đối với mỗi nhóm chỉnh sửa, dòng đầu tiên chứa $k_i$ ($1 \le k_i \le 10^5$), cho biết số lượng chỉnh sửa trong nhóm này.
$k_i$ dòng tiếp theo mỗi dòng chứa ba số nguyên $p_j, x_j, y_j$ ($1 \le p_j, x_j \le n, 1 \le y_j \le 10^6$), cho biết $a_{p_j}$ được sửa thành $x_j$ và $c_{p_j}$ được sửa thành $y_j$.
Đảm bảo rằng $p_1 < p_2 < \dots < p_{k_i}$.
Dữ liệu ra
In ra tổng cộng $q + 1$ dòng, mỗi dòng chứa một số thực dấu phẩy động biểu thị đáp án.
Dòng đầu tiên là đáp án cho mảng ban đầu, theo sau là $q$ dòng cho đáp án sau mỗi nhóm chỉnh sửa.
Một đáp án được coi là đúng nếu sai số tương đối hoặc tuyệt đối so với đáp án chuẩn không vượt quá $10^{-9}$.
Ví dụ
Dữ liệu vào 1
2 1 2 1 1 2 1 2 1 2 1 1 1 2
Dữ liệu ra 1
1.333333333333 3.000000000000 4.000000000000
Dữ liệu vào 2
6 1 1 4 5 1 4 2 3 3 3 3 3 0
Dữ liệu ra 2
9.013888888889
Ghi chú
Bài toán này có kích thước dữ liệu vào lớn, vui lòng sử dụng phương pháp nhập dữ liệu hiệu quả.