Є масив $a$ довжини $n$, де $i$-те число дорівнює $a_i$. Крім того, кожне число має бали, і кількість балів $i$-го числа дорівнює $c_i$. Аліса та Боб ходять по черзі, першою ходить Аліса.
У поточному раунді гравець спочатку копіює масив $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]$ (тобто префікс довжини $k$ масиву $a$) та отримати бали видалених чисел. Гра закінчується, коли масив $a$ стає порожнім.
Зверніть увагу, що сам масив $a$ та масив його балів $c$ протягом усього процесу не перемішуються, а лише видаляються їхні префікси.
І Аліса, і Боб хочуть максимізувати свої бали. Аліса хоче дізнатися, яким є математичне сподівання її балів, якщо обидва гравці дотримуються оптимальних стратегій.
Аліса також зробила $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
Примітка
Ця задача має великий обсяг вхідних даних, будь ласка, використовуйте ефективний метод введення.