Дан массив $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
Примечание
В этой задаче большой объём входных данных, пожалуйста, используйте быстрый метод ввода.