Бесси с коровками играют с последовательностями, и им нужна Ваша помощь. Игра начинается с последовательности, изначально содержащей только одно число 0, во время игры коровки выполняют n операций. Операции бывают следующих типов:
После каждой операции коровкам интересно знать среднее арифметическое всех чисел в последовательности. Помогите им!
Первая строка содержит единственное целое число n (1 ≤ n ≤ 2·105) — количество операций. Следующие n строк описывают операции. Каждая строка начинается с целого числа ti (1 ≤ ti ≤ 3), обозначающего тип операции (см. выше). Если ti = 1, то за ним последуют два целых числа ai, xi (|xi| ≤ 103; 1 ≤ ai). Если ti = 2, то за ним последует единственное целое число ki (|ki| ≤ 103). Если ti = 3, то за ним ничего не последует.
Гарантируется, что все операции корректны (не затрагивают несуществующих элементов) и что в последовательности всегда будет хотя бы одно целое число.
Выведите n строк, в каждой должно содержаться среднее арифметическое всех чисел в последовательности после выполнения соответствующей операции.
Ответ считается корректным, если абсолютная или относительная погрешность не превышает 10 - 6.
Во втором примере последовательность преобразуется следующим образом:
5 2 1 3 2 3 2 1 3
0.500000 0.000000 1.500000 1.333333 1.500000
6 2 1 1 2 20 2 2 1 2 -3 3 3
0.500000 20.500000 14.333333 12.333333 17.500000 17.000000
1500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач