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 Inf = 0x3f3f3f3f;
  const int maxnds = 3000005, maxm = 50005;
  int N, M;
  long long NN;
  int op[maxm], ans[maxm];
  long long lp[maxm], rp[maxm];
  int son[maxnds][2], rt, nds;
  int bel[maxnds];
  map<long long, int> pos[55];
  char tmp[20];
  vector<pair<long long, long long> > ars;
  vector<pair<int, int> > egs[maxm];
  struct Segment {
    long long l, r;
    int id, p;
  };
  vector<Segment> ss;
  struct UnionFind {
    int fa[maxnds];
    UnionFind() { memset(fa, -1, sizeof(fa)); }
    int inline root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); }
    bool inline conn(int a, int b) {
      a = root(a);
      b = root(b);
      if (a == b) return 0;
      if (fa[a] < fa[b]) swap(a, b);
      return fa[b] += fa[a], fa[a] = b, 1;
    }
  } uf;
  void inline build(long long l, long long r, int id, int &now, int dep = 0,
                    long long nl = 0, long long nr = NN - 1) {
    if (nl > r || nr < l) return;
    if (!now) now = ++nds;
    if (nl >= l && nr <= r) {
      bel[now] = id;
      pos[dep][nl] = now;
      return;
    }
    long long m = (nl + nr) >> 1;
    build(l, r, id, son[now][0], dep + 1, nl, m);
    build(l, r, id, son[now][1], dep + 1, m + 1, nr);
  }
  pair<int, int> inline solve(int now, long long nl = 0, long long nr = NN - 1) {
    if (bel[now]) {
      ss.push_back({nl, nr, bel[now], now});
      return make_pair(((int)(ss).size()) - 1, ((int)(ss).size()) - 1);
    }
    long long m = (nl + nr) >> 1, nmd = m - nl + 1;
    pair<int, int> ls = solve(son[now][0], nl, m);
    pair<int, int> rs = solve(son[now][1], m + 1, nr);
    for (int i = ls.first, j = rs.first; i <= ls.second && j <= rs.second;) {
      if (ss[i].l <= ss[j].r - nmd && ss[j].l - nmd <= ss[i].r) {
        egs[min(ss[i].id, ss[j].id)].emplace_back(ss[i].p, ss[j].p);
      }
      if (ss[i].r <= ss[j].r - nmd)
        ++i;
      else
        ++j;
    }
    return make_pair(ls.first, rs.second);
  }
  int main() {
    scanf("%d%d", &N, &M);
    NN = 1ll << N;
    for (int i = 1; i <= (M); ++i) {
      scanf("%s", tmp);
      scanf("%lld%lld", lp + i, rp + i);
      op[i] = 'b' - tmp[0];
      if (!op[i]) {
        ars.emplace_back(lp[i], rp[i]);
        build(lp[i], rp[i], i, rt);
      }
    }
    sort(ars.begin(), ars.end());
    long long lst = 0;
    for (int i = 0; i < (((int)(ars).size())); ++i) {
      if (lst < ars[i].first) build(lst, ars[i].first - 1, M + 1, rt);
      lst = ars[i].second + 1;
    }
    if (lst < NN) build(lst, NN - 1, M + 1, rt);
    solve(rt);
    for (int i = M + 1; i; --i) {
      for (auto &e : egs[i]) uf.conn(e.first, e.second);
      if (op[i]) {
        int lvl = N, lvr = N;
        long long ls = lp[i], rs = rp[i];
        while (!pos[lvl].count(ls)) {
          if ((ls >> (N - lvl)) & 1) ls ^= 1ll << (N - lvl);
          --lvl;
        }
        while (!pos[lvr].count(rs)) {
          if ((rs >> (N - lvr)) & 1) rs ^= 1ll << (N - lvr);
          --lvr;
        }
        ans[i] = uf.root(pos[lvl][ls]) == uf.root(pos[lvr][rs]);
      }
    }
    for (int i = 1; i <= (M); ++i)
      if (op[i]) printf("%d\n", ans[i]);
    return 0;
  }
  