description: <image>
  
  As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from 0 to 2^n - 1. On each planet, there are gates that allow the player to move from planet i to planet j if the binary representations of i and j differ in exactly one bit.
  
  William wants to test you and see how you can handle processing the following queries in this game universe:
  
    * Destroy planets with numbers from l to r inclusively. These planets cannot be moved to anymore.
    * Figure out if it is possible to reach planet b from planet a using some number of planetary gates. It is guaranteed that the planets a and b are not destroyed. 
  
  Input
  
  The first line contains two integers n, m (1 ≤ n ≤ 50, 1 ≤ m ≤ 5 ⋅ 10^4), which are the number of bits in binary representation of each planets' designation and the number of queries, respectively.
  
  Each of the next m lines contains a query of two types:
  
  block l r — query for destruction of planets with numbers from l to r inclusively (0 ≤ l ≤ r < 2^n). It's guaranteed that no planet will be destroyed twice.
  
  ask a b — query for reachability between planets a and b (0 ≤ a, b < 2^n). It's guaranteed that planets a and b hasn't been destroyed yet.
  
  Output
  
  For each query of type ask you must output "1" in a new line, if it is possible to reach planet b from planet a and "0" otherwise (without quotation marks).
  
  Examples
  
  Input
  
  
  3 3
  ask 0 7
  block 3 6
  ask 0 7
  
  
  Output
  
  
  1
  0
  
  
  Input
  
  
  6 10
  block 12 26
  ask 44 63
  block 32 46
  ask 1 54
  block 27 30
  ask 10 31
  ask 11 31
  ask 49 31
  block 31 31
  ask 2 51
  
  
  Output
  
  
  1
  1
  0
  0
  1
  0
  
  Note
  
  The first example test can be visualized in the following way:
  
  <image>
  
  Response to a query ask 0 7 is positive.
  
  Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):
  
  <image>
  
  Response to a query ask 0 7 is negative, since any path from vertex 0 to vertex 7 must go through one of the destroyed vertices.
solution: #include <bits/stdc++.h>
  int n, m;
  char str[50005];
  std::pair<long long, long long> q[50005];
  std::vector<std::pair<int, int>> E[50005];
  struct node {
    int id, col;
    node *son[2];
    node(int id_ = 0) {
      id = id_;
      col = 0;
      son[0] = son[1] = 0;
    }
    inline bool lf() { return !son[0]; }
  } * rt;
  int tot;
  inline void pshd(node *p) {
    if (!p->son[0]) p->son[0] = new node(++tot);
    if (!p->son[1]) p->son[1] = new node(++tot);
    if (p->col) {
      p->son[0]->col = p->son[1]->col = p->col;
      p->col = 0;
    }
  }
  inline void ins(node *p, long long L, long long R, long long l, long long r,
                  int t) {
    if (L > r || R < l) return;
    if (l <= L && R <= r) {
      p->col = t;
      return;
    }
    pshd(p);
    long long mid = (L + R) >> 1;
    ins(p->son[0], L, mid, l, r, t);
    ins(p->son[1], mid + 1, R, l, r, t);
  }
  inline void sol(node *x, node *y) {
    if (x->lf() && y->lf()) {
      E[std::min(x->col, y->col)].push_back({x->id, y->id});
      return;
    }
    sol(x->lf() ? x : x->son[0], y->lf() ? y : y->son[0]);
    sol(x->lf() ? x : x->son[1], y->lf() ? y : y->son[1]);
  }
  inline void dfs(node *p) {
    if (p->lf()) return;
    sol(p->son[0], p->son[1]);
    dfs(p->son[0]), dfs(p->son[1]);
  }
  inline node *pos(node *p, long long L, long long R, long long x) {
    if (p->lf()) return p;
    long long mid = (L + R) >> 1;
    if (x <= mid)
      return pos(p->son[0], L, mid, x);
    else
      return pos(p->son[1], mid + 1, R, x);
  }
  int f[50005 << 8];
  inline int fnd(int x) { return ~f[x] ? f[x] = fnd(f[x]) : x; }
  inline void mrg(int u, int v) {
    if (fnd(u) != fnd(v)) f[fnd(u)] = fnd(v);
  }
  int ans[50005];
  int main() {
    scanf("%d%d", &n, &m);
    rt = new node(++tot);
    rt->col = m + 1;
    for (int i = 1; i <= m + 1; i++) q[i] = {-1, -1};
    for (int i = 1; i <= m; i++) {
      long long u, v;
      scanf("%s%lld%lld", str, &u, &v);
      if (str[0] == 'a')
        q[i] = {u, v};
      else
        ins(rt, 0, (1ll << n) - 1, u, v, i);
    }
    dfs(rt);
    memset(f, -1, sizeof(f));
    for (int i = m + 1; i; i--) {
      for (auto [u, v] : E[i]) mrg(u, v);
      auto [u, v] = q[i];
      if (~u)
        ans[i] = fnd(pos(rt, 0, (1ll << n) - 1, u)->id) ==
                 fnd(pos(rt, 0, (1ll << n) - 1, v)->id);
    }
    for (int i = 1; i <= m; i++)
      if (~q[i].first) printf("%d\n", ans[i]);
  }
  