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.
First line will contain two integers *h* and *q* (1 ≤ *h* ≤ 30, 1 ≤ *q* ≤ 10<sup class="upper-index">5</sup>). 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<sup class="upper-index">*h* + 1</sup> - 1, 0 ≤ *e* ≤ 10<sup class="upper-index">4</sup>). *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.-  decayPetya induces tree decay.
none
1 4
add 1 3
add 2 10
add 3 11
decay
13.50000000
3 6
decay
decay
add 6 872
decay
add 13 813
add 8 531
0.00000000
0.00000000
872.00000000
3 6
add 2 101
add 6 830
add 11 899
add 2 421
decay
decay
1290.50000000
1290.50000000
3 6
add 11 467
add 9 879
decay
add 15 551
add 14 473
add 14 104
1112.50000000
9 6
add 593 652
decay
decay
decay
decay
decay
652.00000000
652.00000000
652.00000000
652.00000000
652.00000000
7 10
decay
add 10 9923
decay
add 21 2047
decay
add 4 8696
decay
decay
add 204 4988
add 230 1977
0.00000000
9923.00000000
11842.06250000
16190.06250000
16190.06250000
7 50
decay
decay
decay
decay
decay
decay
decay
add 121 5677
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
add 102 1582
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
decay
add 187 7032
add 194 6485
decay
decay
decay
decay
decay
decay
decay
add 202 6898
decay
decay
decay
decay
decay
decay
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
5677.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
6468.00000000
10776.12500000
10776.12500000
10776.12500000
1077...
print("_RANDOM_GUESS_1689447913.794764")# 1689447913.7947829