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. 

Input

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 ≤ 2h + 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 2x and 2x + 1.

  * decay

Petya induces tree decay. 

Output

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.

Examples

Input

1 4
add 1 3
add 2 10
add 3 11
decay


Output

13.50000000
#include <bits/stdc++.h>
using namespace std;
namespace output {
void __(short x) { cout << x; }
void __(unsigned x) { cout << x; }
void __(int x) { cout << x; }
void __(long long x) { cout << x; }
void __(unsigned long long x) { cout << x; }
void __(double x) { cout << x; }
void __(long double x) { cout << x; }
void __(char x) { cout << x; }
void __(const char* x) { cout << x; }
void __(const string& x) { cout << x; }
void __(bool x) { cout << (x ? "true" : "false"); }
template <class S, class T>
void __(const pair<S, T>& x) {
  __(1 ? "(" : ""), __(x.first), __(1 ? ", " : " "), __(x.second),
      __(1 ? ")" : "");
}
template <class T>
void __(const vector<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const set<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class T>
void __(const multiset<T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
template <class S, class T>
void __(const map<S, T>& x) {
  __(1 ? "{" : "");
  bool _ = 0;
  for (const auto& v : x) __(_ ? 1 ? ", " : " " : ""), __(v), _ = 1;
  __(1 ? "}" : "");
}
void pr() { cout << "\n"; }
template <class S, class... T>
void pr(const S& a, const T&... b) {
  __(a);
  if (sizeof...(b)) __(' ');
  pr(b...);
}
}  // namespace output
using namespace output;
const int MN = 33;
int h, q, i, x, y;
string s;
map<int, int> sm, val;
int main() {
  scanf("%d%d", &h, &q);
  for (; q; q--) {
    cin >> s;
    if (s == "add") {
      scanf("%d%d", &x, &y);
      val[x] += y;
      while (x) {
        sm[x] += y;
        x >>= 1;
      }
    } else {
      x = 1;
      int mx = 0;
      double prob = 1, ans = 0;
      for (i = 0; i < h; i++) {
        int lsum = val[x] + sm[x << 1], rsum = val[x] + sm[(x << 1) | 1];
        if (lsum > rsum) {
          ans += prob / 2.0 * max(mx, lsum);
          mx = max(mx, rsum);
          x = (x << 1);
        } else {
          ans += prob / 2.0 * max(mx, rsum);
          mx = max(mx, lsum);
          x = (x << 1) | 1;
        }
        prob /= 2;
      }
      ans += prob * max(mx, val[x]);
      printf("%.6lf\n", ans);
    }
  }
  return 0;
}
