E. День рождения ослика Иа-Иа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У ослика Иа-Иа сегодня день рождения. Его друг, Винни-Пух, хочет сделать ему самый лучший подарок — горшочек меда. Конечно, медвежонок понимает, что полный горшочек до ослика донести не удастся, потому что по пути он съест весь мед. А раз уж Винни собрался перекусить по пути, то изначально в горшочке должно быть как можно больше меда.

За день до этого Винни-Пух пополнил свои запасы меда. Дома у Винни-Пуха есть n полок, на каждой из которых находится некоторое, возможно нулевое, количество горшочков с медом. В течение дня Винни q раз подходил к полкам с медом; в i-тый раз он подходил к некоторой полке ui, брал с нее некоторое количество горшочков ki, пробовал мед из каждого из них и ставил все эти горшочки на некоторую полку vi. Выбирая горшочки, Винни руководствовался интуицией, а, значит, можно считать, что среди всех наборов из ki горшочков на полке ui, он равновероятно выбирает один.

Сейчас Винни помнит все действия, которые он выполнял с горшочками меда. На праздник он хочет взять горшочек, который вчера ему не попадался. Для этого ему необходимо знать математическое ожидание m количества полок, на которых нет ни одного нетронутого медвежонком горшочка. Для того, чтобы лучше оценить свои шансы, Винни-Пух хочет знать значение m после каждого выполненного им действия.

Ваша задача — написать программу, которая найдет эти значения за него.

Входные данные

Первая строка входных данных содержит единственное целое число n (1 ≤ n ≤ 105) — количество полок у Винни-Пуха дома. Вторая строка содержит n целых чисел ai (1 ≤ i ≤ n, 0 ≤ ai ≤ 100) — количество горшочков с медом на полке с номером i.

В следующей строке содержится целое число q (1 ≤ q ≤ 105) — количество действий, которое выполнил Винни за предыдущий день. Далее следует q строк, i-ая из которых описывает очередное в хронологическом порядке действие и содержит три целых числа ui, vi и ki (1 ≤ ui, vi ≤ n, 1 ≤ ki ≤ 5) — номер полки, с которой Винни взял горшочки, номер полки, на которую Винни поставил горшочки после того, как попробовал мед из каждого из них, и количество горшочков, из которых Винни-Пух попробовал мёд, соответственно.

Считайте, что полки с горшочками пронумерованы целыми числами от 1 до n. Гарантируется, что Винни-Пух никогда не пытался брать с полки больше горшков, чем на ней находится.

Выходные данные

Для каждого действия Винни-Пуха выведите величину математического ожидания m на момент окончания выполнения этого действия. Относительная или абсолютная погрешность каждого значения не должна превышать 10 - 9.

Примеры
Входные данные
3
2 2 3
5
1 2 1
2 1 2
1 2 2
3 1 1
3 2 2
Выходные данные
0.000000000000
0.333333333333
1.000000000000
1.000000000000
2.000000000000