← 返回题目列表

Codeforces · 283/A

A. 奶牛和序列

中文机器翻译题面 查看原题

贝西和奶牛正在玩序列,需要你的帮助。它们从一个序列开始,最初只包含数字 0,并执行 n 个操作。每个操作都是以下操作之一:

1. 将整数 xi 添加到序列的前 ai 元素中。
2. 将整数ki 附加到序列末尾。 (因此序列的大小增加 1)
3. 删除序列的最后一个元素。因此,序列的大小减一。请注意,只有当序列中至少有两个元素时才能执行此操作。

每次操作后,奶牛都想知道序列中所有数字的平均值。帮助他们!

输入

第一行包含一个整数 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,则认为答案是正确的。

示例

输入 #1

5
2 1
3
2 3
2 1
3

输出 #1

0.500000
0.000000
1.500000
1.333333
1.500000

输入 #2

6
2 1
1 2 20
2 2
1 2 -3
3
3

输出 #2

0.500000
20.500000
14.333333
12.333333
17.500000
17.000000

注意

在第二个示例中,序列变为 $$\{0\} \rightarrow \{0,1\} \rightarrow \{20,21\} \rightarrow \{20,21,2\} \rightarrow \{17,18,2\} \rightarrow \{17\}。$$