贝西和奶牛正在玩序列,需要你的帮助。它们从一个序列开始,最初只包含数字 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\}。$$