最近Petya开始热衷于物理。他的老师安娜·V.注意到了佩蒂亚的兴趣,并给了他一个令人着迷的物理难题——一棵半腐烂的树。
半衰树是高度为 h 的完全二叉树。树的高度是从树根到叶子的路径长度(以边为单位)。在研究树时,Petya 可以向顶点添加电子或使用同步相加速器引发随机衰变。随机衰减是删除从树的根到随机叶子的某些路径的边缘的过程。所有叶子都是等概率的。由于半腐烂的树是学校财产,Petya 会在每次腐烂后将删除的边返回到树中。
分解后,树分解为连接的组件。每个组件的电荷是放置在组件顶点的电子总量。解体树的势是其连接组件的电荷的最大值。每次在引发随机腐烂之前,Petya 都会对树解体后潜力的数学期望感到好奇。
输入
第一行将包含两个整数 h 和 q (1 ≤ h ≤ 30, 1 ≤ q ≤ 105)。接下来的 q 行将包含以下两种类型之一的查询:
- add v ePetya 将 e 个电子添加到顶点编号 v (1 ≤ v ≤ 2h + 1 - 1, 0 ≤ e ≤ 104)。 v和e是整数。树的顶点按以下方式编号:根编号为1,编号为x的顶点的子节点编号为2x和2x + 1。
- 腐烂Petya 会导致树木腐烂。
输出
对于每个查询衰减解决方案,您应该输出分解后树势的数学期望。答案的绝对或相对误差不应超过 10 - 4。
示例
输入 #1
1 4 add 1 3 add 2 10 add 3 11 decay
输出 #1
13.50000000