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 N = (int)5e4 + 5;
  vector<pair<long long, long long> > segs, sg;
  vector<pair<int, int> > ins[N];
  int pr[40 * N];
  long long l[N], r[N];
  int n, q;
  int tp[N], ans[N];
  void div(int bit, long long l, long long r) {
    long long siz = (1ll << (bit + 1)) - 1;
    long long l_s = l & siz;
    long long r_s = r & siz;
    if (!l_s && r_s == siz) {
      segs.push_back({l, r});
      return;
    }
    if (l_s >= (1ll << bit)) {
      div(bit - 1, l, r);
    } else {
      if (r_s < (1ll << bit)) {
        div(bit - 1, l, r);
      } else {
        long long md = l | ((1ll << bit) - 1);
        div(bit - 1, l, md);
        div(bit - 1, md + 1, r);
      }
    }
  }
  int f(int v) { return (pr[v] == v ? v : pr[v] = f(pr[v])); }
  void link(int v, int u) {
    v = f(v);
    u = f(u);
    if (v == u) {
      return;
    }
    pr[u] = v;
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
      cin >> s >> l[i] >> r[i];
      if (s == "ask") {
        tp[i] = 0;
      } else {
        tp[i] = 1;
        sg.push_back({l[i], r[i]});
      }
    }
    vector<pair<long long, long long> > nsg;
    sort((sg).begin(), (sg).end());
    if ((int)sg.size() == 0) {
      sg.push_back({0, (1ll << n) - 1});
    }
    if (sg[0].first != 0) {
      nsg.push_back({0, sg[0].first - 1});
    }
    for (int i = 0; i < (int)sg.size(); i++) {
      nsg.push_back(sg[i]);
      if (i + 1 < (int)sg.size() && sg[i].second + 1 <= sg[i + 1].first - 1) {
        nsg.push_back({sg[i].second + 1, sg[i + 1].first - 1});
      }
    }
    if (sg.back().second + 1 <= (1ll << n) - 1) {
      nsg.push_back({sg.back().second + 1, (1ll << n) - 1});
    }
    for (auto &x : nsg) {
      div(n - 1, x.first, x.second);
    }
    vector<int> tm((int)segs.size());
    for (int i = 0; i < (int)segs.size(); i++) {
      tm[i] = -1;
    }
    for (int i = 0; i < q; i++) {
      if (!tp[i]) {
        continue;
      }
      int L = lower_bound((segs).begin(), (segs).end(), make_pair(l[i], -1ll)) -
              segs.begin();
      int R =
          lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
          segs.begin();
      for (int j = L; j < R; j++) {
        tm[j] = i;
      }
    }
    for (int i = 0; i < (int)segs.size(); i++) {
      if (tm[i] == -1) {
        tm[i] = q;
      }
    }
    vector<int> sb[2];
    for (int i = 0; i < n; i++) {
      sb[0].clear();
      sb[1].clear();
      for (int j = 0; j < (int)segs.size(); j++) {
        long long L = segs[j].first;
        long long R = segs[j].second;
        if ((1ll << i) >= R - L + 1) {
          assert(((R >> i) & 1) == ((L >> i) & 1));
          sb[((R >> i) & 1)].push_back(j);
        }
      }
      for (int b = 0; b < 2; b++) {
        int p = 0;
        for (int j = 0; j < (int)sb[b].size(); j++) {
          int id = sb[b][j];
          long long L = segs[id].first ^ (1ll << i);
          while (segs[p].second < L) {
            p++;
          }
          if (segs[p].second - segs[p].first >=
              segs[id].second - segs[id].first) {
            int tim = min(tm[p], tm[id]);
            ins[tim].push_back({p, id});
          }
        }
      }
    }
    for (int i = 0; i < (int)segs.size(); i++) {
      pr[i] = i;
    }
    for (int i = q; i >= 0; i--) {
      for (auto &x : ins[i]) {
        link(x.first, x.second);
      }
      if (i < q && !tp[i]) {
        int v =
            lower_bound((segs).begin(), (segs).end(), make_pair(l[i] + 1, -1ll)) -
            segs.begin() - 1;
        int u =
            lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
            segs.begin() - 1;
        ans[i] = (f(v) == f(u));
      }
    }
    for (int i = 0; i < q; i++) {
      if (!tp[i]) {
        cout << ans[i] << '\n';
      }
    }
  }
  