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>
  using namespace std;
  const int maxn = 5e4 + 5;
  long long l[maxn], r[maxn];
  int op[maxn], root, id[maxn * 100], tot, idtot, ls[maxn * 100], rs[maxn * 100],
      ban[maxn * 100], fa[maxn * 100], n;
  vector<int> has[maxn], g[maxn * 100];
  void add(int &rt, long long l, long long r, long long ql, long long qr) {
    if (!rt) rt = ++tot;
    if (l >= ql && r <= qr) {
      id[rt] = ++idtot;
      return;
    }
    long long mid = l + r >> 1;
    if (ql <= mid) add(ls[rt], l, mid, ql, qr);
    if (qr >= mid + 1) add(rs[rt], mid + 1, r, ql, qr);
  }
  void getedge(int L, int R, int cur, int limt) {
    if (!L || !R) return;
    if (cur > limt) {
      getedge(ls[L], ls[R], cur - 1, limt);
      getedge(rs[L], rs[R], cur - 1, limt);
      return;
    }
    if (cur == limt) {
      getedge(ls[L], rs[R], cur - 1, limt);
      return;
    }
    if (id[L] && id[R]) {
      g[id[L]].push_back(id[R]);
      g[id[R]].push_back(id[L]);
      return;
    }
    if (id[L]) {
      getedge(L, ls[R], cur - 1, limt);
      getedge(L, rs[R], cur - 1, limt);
      return;
    }
    if (id[R]) {
      getedge(ls[L], R, cur - 1, limt);
      getedge(rs[L], R, cur - 1, limt);
      return;
    }
    getedge(ls[L], ls[R], cur - 1, limt);
    getedge(rs[L], rs[R], cur - 1, limt);
  }
  void getpoint(int rt, long long l, long long r, int i, long long ql,
                long long qr) {
    if (l >= ql && r <= qr) {
      has[i].push_back(id[rt]);
      ban[id[rt]] = 1;
      return;
    }
    long long mid = l + r >> 1;
    if (ql <= mid) getpoint(ls[rt], l, mid, i, ql, qr);
    if (qr >= mid + 1) getpoint(rs[rt], mid + 1, r, i, ql, qr);
  }
  int fd(int rt) { return rt == fa[rt] ? rt : (fa[rt] = fd(fa[rt])); }
  void merge(int u, int v) {
    if (fd(u) == fd(v)) return;
    fa[fd(u)] = fd(v);
  }
  void insert(int x) {
    fa[x] = x;
    for (auto u : g[x]) {
      if (fa[u]) merge(x, u);
    }
  }
  int getbl(long long x) {
    int u = root;
    if (id[u]) return id[u];
    for (int i = n - 1; i >= 0; --i) {
      if ((x >> i) & 1) {
        u = rs[u];
      } else
        u = ls[u];
      if (id[u]) return id[u];
    }
  }
  int main() {
    int m;
    vector<long long> x;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
      char s[5];
      scanf("%s%lld%lld", s, l + i, r + i);
      if (s[0] == 'b') {
        x.push_back(l[i] - 1);
        x.push_back(r[i]);
      } else
        op[i] = 1;
    }
    long long mx = (1ll << n) - 1;
    x.push_back(-1);
    x.push_back(mx);
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    for (int i = 1; i < x.size(); ++i) add(root, 0, mx, x[i - 1] + 1, x[i]);
    for (int i = 0; i < n; ++i) getedge(root, root, n - 1, i);
    for (int i = 0; i < m; ++i)
      if (!op[i]) getpoint(root, 0, mx, i, l[i], r[i]);
    for (int i = 1; i <= idtot; ++i)
      if (!ban[i]) insert(i);
    vector<int> ans;
    for (int i = m - 1; i >= 0; --i) {
      l[i] = getbl(l[i]), r[i] = getbl(r[i]);
      if (op[i]) {
        ans.push_back(fd(l[i]) == fd(r[i]));
      } else {
        for (auto u : has[i]) {
          insert(u);
        }
      }
    }
    for (int i = (int)ans.size() - 1; i >= 0; --i) printf("%d\n", ans[i]);
  }
  