CF68D.Half-decay tree

Recently Petya has become keen on physics. Anna V., his teacher noticed Petya's interest and gave him a fascinating physical puzzle — a half-decay tree.

A half-decay tree is a complete binary tree with the height h. The height of a tree is the length of the path (in edges) from the root to a leaf in the tree. While studying the tree Petya can add electrons to vertices or induce random decay with synchrophasotron. Random decay is a process during which the edges of some path from the root to the random leaf of the tree are deleted. All the leaves are equiprobable. As the half-decay tree is the school property, Petya will return back the deleted edges into the tree after each decay.

After being desintegrated, the tree decomposes into connected components. Charge of each component is the total quantity of electrons placed in vertices of the component. Potential of desintegerated tree is the maximum from the charges of its connected components. Each time before inducing random decay Petya is curious about the mathematical expectation of potential of the tree after being desintegrated.

最近，佩佳对物理学产生了浓厚兴趣。他的老师安娜·V. 注意到了佩佳的兴趣，便给了他一个引人入胜的物理谜题——“半衰树”。

半衰树是一棵高度为 $h$ 的满二叉树。树的高度定义为从根节点到任意叶节点的路径长度（以边数计）。在研究这棵树的过程中，佩佳可以向顶点添加电子，或使用同步相位加速器（synchrophasotron）触发随机衰变。所谓随机衰变，是指随机选择一条从根节点到某个叶节点的路径，并将该路径上的所有边全部删除；所有叶节点被选中的概率均等。由于这棵半衰树属于学校财产，每次衰变后，佩佳都会将被删除的边重新恢复至树中。

衰变之后，树将分解为若干个连通分量。每个连通分量的电荷量定义为该分量内所有顶点上电子总数。而衰变后整棵树的势能，则定义为所有连通分量电荷量的最大值。每次触发随机衰变之前，佩佳都很好奇：衰变后树的势能的数学期望值是多少？

First line will contain two integers h and q (1 ≤ h ≤ 30, 1 ≤ q ≤ 105). Next q lines will contain a query of one of two types:

• add v e

  Petya adds e electrons to vertex number v (1 ≤ v ≤ 2_h_ + 1 - 1, 0 ≤ e ≤ 104). v and e are integers.

  The vertices of the tree are numbered in the following way: the root is numbered with 1, the children of the vertex with number x are numbered with 2_x_ and 2_x_ + 1.

• decay

  Petya induces tree decay.

第一行包含两个整数 $h$ 和 $q$（$1 \le h \le 30$，$1 \le q \le 10^5$）。接下来的 $q$ 行每行包含以下两种类型之一的查询：

• add v e
  Petya 向编号为 $v$ 的顶点添加 $e$ 个电子（$1 \le v \le 2^{h+1} - 1$，$0 \le e \le 10^4$），其中 $v$ 和 $e$ 均为整数。
  树中顶点的编号规则如下：根节点编号为 $1$，编号为 $x$ 的顶点的两个子节点编号分别为 $2x$ 和 $2x + 1$。

• decay
  Petya 触发树的衰变。

For each query decay solution you should output the mathematical expectation of potential of the tree after being desintegrated. The absolute or relative error in the answer should not exceed 10 - 4.

对于每个查询衰减解，您应输出树在解体后的势能的数学期望值。答案的绝对或相对误差不应超过 $10^{-4}$。