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>
  namespace {
  using LL = long long;
  struct Dsu {
    int n;
    std::vector<int> dsu;
    explicit Dsu(int n) : n(n), dsu(n) { std::iota(dsu.begin(), dsu.end(), 0); }
    int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
    bool is_connected(int x, int y) {
      x = find(x);
      y = find(y);
      return x == y;
    }
    bool merge(int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) return false;
      dsu[x] = y;
      return true;
    }
  };
  struct Operation {
    std::string op;
    LL x, y;
  };
  struct Solver {
    int n, m;
    std::vector<Operation> ops;
    void solve(int ca, std::istream& reader) {
      reader >> n >> m;
      std::vector<LL> ss{0, (1LL << n)};
      for (int i = 0; i < m; ++i) {
        std::string op;
        LL x, y;
        reader >> op >> x >> y;
        ops.emplace_back(Operation{.op = op, .x = x, .y = y});
        if (op == "block") {
          ss.emplace_back(x);
          ss.emplace_back(y + 1);
        }
      }
      std::sort(ss.begin(), ss.end());
      ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
      ;
      for (int i = (int)ss.size() - 2; i >= 0; --i) {
        LL l = ss[i];
        LL r = ss[i + 1] - 1;
        int k = 0;
        while ((l >> k) != (r >> k)) {
          ++k;
        }
        if (k) {
          ss.emplace_back(r >> (k - 1) << (k - 1));
        }
      }
      std::sort(ss.begin(), ss.end());
      ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
      int tot = (int)ss.size() - 1;
      std::vector<std::vector<int>> graph(tot);
      Dsu dsu(tot);
      auto link = [&](int i, int j, int k) -> void {
        LL l = std::max(ss[i], ss[j] - (1LL << k));
        LL r = std::min(ss[i + 1], ss[j + 1] - (1LL << k)) - 1;
        assert(l <= r);
        if ((~l >> k & 1) || (~r >> k & 1) || (l >> k) != (r >> k)) {
          graph[i].emplace_back(j);
          graph[j].emplace_back(i);
        }
      };
      for (int k = 0; k < n; ++k) {
        LL d = 1LL << k;
        for (int i = 0, j = 0; i < tot; ++i) {
          while (j < tot && ss[j + 1] <= ss[i] + d) {
            ++j;
          }
          while (j < tot && ss[j + 1] <= ss[i + 1] + d) {
            link(i, j, k);
            ++j;
          }
          if (j < tot && ss[j] < ss[i + 1] + d) {
            link(i, j, k);
          }
        }
      };
      std::vector<char> mark(tot, true);
      for (int i = 0; i < m; ++i)
        if (ops[i].op == "block") {
          int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
          int r =
              std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
          for (int j = l; j < r; ++j) {
            mark[j] = false;
          }
        }
      for (int i = 0; i < tot; ++i)
        if (mark[i]) {
          for (int j : graph[i])
            if (mark[j]) {
              dsu.merge(i, j);
            }
        }
      std::vector<int> result(m, 0);
      for (int i = m - 1; i >= 0; --i) {
        if (ops[i].op == "block") {
          int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
          int r =
              std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
          for (int j = l; j < r; ++j) {
            mark[j] = true;
            for (int w : graph[j])
              if (mark[w]) {
                dsu.merge(j, w);
              }
          }
        } else {
          int x =
              std::upper_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin() - 1;
          int y =
              std::upper_bound(ss.begin(), ss.end(), ops[i].y) - ss.begin() - 1;
          result[i] = dsu.is_connected(x, y);
        }
      }
      for (int i = 0; i < m; ++i) {
        if (ops[i].op != "block") {
          printf("%d\n", result[i]);
        }
      }
    }
  };
  }  // namespace
  int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::istream& reader = std::cin;
    int cas = 1;
    for (int ca = 1; ca <= cas; ++ca) {
      Solver().solve(ca, reader);
    }
  }
  