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;
  struct Val {
    long long v;
    long long* pos;
    bool operator<(const Val& y) const { return v < y.v; }
  } ar[200010], qs[100010];
  int n, m, op[50010], tmp, num, sz, s2, nw, f[200010], de[200010], prt[50010];
  long long nul, a[50010], b[50010], mp[200010];
  char s[10];
  vector<int> e[200010], d[200010];
  void Ins(const int& x, const int& y, const int& t) {
    long long l = max(mp[x], mp[y] - (1ll << t)),
              r = min(mp[x + 1] - 1, mp[y + 1] - (1ll << t) - 1);
    if (!((l >> t) & 1) || (l >> t) != (r >> t))
      e[x].push_back(y), e[y].push_back(x);
  }
  int getf(const int& x) { return f[x] == x ? x : f[x] = getf(f[x]); }
  void Merge(int x, int y) {
    if ((x = getf(x)) == (y = getf(y))) return;
    f[x] = y;
  }
  int main() {
    scanf("%d%d", &n, &m);
    ar[++sz] = (Val){0, &nul}, ar[++sz] = (Val){1ll << n, &nul};
    for (int i = 1; i <= m; ++i) {
      scanf("%s%lld%lld", s, &a[i], &b[i]), op[i] = (s[0] == 'b');
      if (op[i])
        ar[++sz] = (Val){a[i], &a[i]}, ar[++sz] = (Val){b[i] + 1, &b[i]};
      else
        qs[++s2] = (Val){a[i], &a[i]}, qs[++s2] = (Val){b[i], &b[i]};
    }
    sort(ar + 1, ar + sz + 1), ar[0].v = -1;
    for (int i = 1, ts = sz; i <= ts; ++i)
      if (ar[i - 1].v + 1 < ar[i].v) {
        for (int j = n - 1; j >= 0; --j)
          if ((ar[i - 1].v >> j) != (ar[i].v >> j)) {
            tmp = j;
            break;
          }
        ar[++sz] = (Val){ar[i].v & ((1ll << n) - (1ll << tmp)), &nul};
      }
    sort(ar + 1, ar + sz + 1);
    for (int i = 1; i <= sz; ++i)
      num += (ar[i].v != ar[i - 1].v), *ar[i].pos = num, mp[num] = ar[i].v;
    sort(qs + 1, qs + s2 + 1), nw = 1;
    for (int i = 1; i <= s2; ++i) {
      while (qs[i].v >= mp[nw + 1]) ++nw;
      *qs[i].pos = nw;
    }
    for (int t = 0; t < n; ++t) {
      nw = 0;
      for (int i = 1; i < num; ++i) {
        nw = max(nw, i + 1);
        while (nw < num && mp[nw + 1] <= mp[i] + (1ll << t)) ++nw;
        while (nw < num && mp[nw + 1] <= mp[i + 1] + (1ll << t)) Ins(i, nw++, t);
        if (nw < num && mp[nw] < mp[i + 1] + (1ll << t)) Ins(i, nw, t);
      }
    }
    for (int i = 1; i <= num; ++i) f[i] = i, de[i] = 1;
    for (int i = 1; i <= m; ++i)
      if (op[i])
        for (int j = a[i]; j < b[i]; ++j) de[j] = 0;
    for (int i = 1; i < num; ++i)
      if (de[i])
        for (int j = 0; j < e[i].size(); ++j)
          if (de[e[i][j]]) Merge(i, e[i][j]);
    sz = 0;
    for (int i = m; i >= 1; --i) {
      if (op[i]) {
        for (int j = a[i]; j < b[i]; ++j) {
          de[j] = 1;
          for (int k = 0; k < e[j].size(); ++k)
            if (de[e[j][k]]) Merge(j, e[j][k]);
        }
      } else
        prt[++sz] = (getf(a[i]) == getf(b[i]));
    }
    for (int i = sz; i >= 1; --i) putchar(prt[i] + '0'), puts("");
    return 0;
  }
  