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 MAXQ = 5e4;
  const int MAXN = 50;
  int n, q;
  int m, par[MAXQ * MAXN + 10], w[MAXQ * MAXN + 10], curBlockIdx;
  bool isBlock[MAXQ * MAXN + 10];
  vector<int> adj[MAXQ * MAXN + 10];
  vector<pair<long long, long long> > blockRanges;
  char s[10];
  enum QueryType {
    ASK,
    BLOCK,
  };
  struct Query {
    QueryType queryType;
    long long u, v;
    vector<int> vertexIdx;
    int res;
  };
  Query queries[MAXQ];
  struct Vertex {
    pair<long long, long long> range;
    int idx;
    Vertex() {}
    Vertex(const pair<long long, long long>& range, const int& idx)
        : range(range), idx(idx) {}
    bool operator<(const Vertex& other) const {
      return this->range < other.range;
    }
  };
  struct Node {
    list<Vertex> vertices;
    Node *lef, *rig;
    Node() : lef(NULL), rig(NULL) {}
  };
  Node* root = NULL;
  void insert(const long long& u, const long long& v, Node*& node = root,
              const long long& lef = 0, const long long& rig = (1LL << n) - 1) {
    if (node == NULL) node = new Node;
    if (u == lef && v == rig) {
      node->vertices.push_back(Vertex(pair<long long, long long>(lef, rig), ++m));
      if (curBlockIdx != -1) {
        isBlock[m] = true;
        queries[curBlockIdx].vertexIdx.push_back(m);
      }
      return;
    }
    long long mid = (lef + rig) >> 1;
    if (v <= mid)
      insert(u, v, node->lef, lef, mid);
    else if (u > mid)
      insert(u, v, node->rig, mid + 1, rig);
    else {
      insert(u, mid, node->lef, lef, mid);
      insert(mid + 1, v, node->rig, mid + 1, rig);
    }
  }
  void merge(Node*& node, const long long& len) {
    list<Vertex>::iterator iterU = node->lef->vertices.begin(),
                           iterV = node->rig->vertices.begin(), iterUU, iterVV;
    do {
      iterUU = iterU, iterVV = iterV;
      adj[iterU->idx].push_back(iterV->idx);
      adj[iterV->idx].push_back(iterU->idx);
      if (iterU->range.second + len <= iterV->range.second) ++iterUU;
      if (iterV->range.second <= iterU->range.second + len) ++iterVV;
      iterU = iterUU, iterV = iterVV;
    } while (iterU != node->lef->vertices.end() ||
             iterV != node->rig->vertices.end());
    node->vertices.swap(node->lef->vertices);
    node->vertices.splice(node->vertices.end(), node->rig->vertices);
  }
  void init(Node*& node = root, const long long& lef = 0,
            const long long& rig = (1LL << n) - 1) {
    if (!node->vertices.empty()) return;
    long long mid = (lef + rig) >> 1;
    init(node->lef, lef, mid);
    init(node->rig, mid + 1, rig);
    merge(node, mid - lef + 1);
  }
  int findRoot(const int& u) {
    if (u == par[u]) return u;
    return par[u] = findRoot(par[u]);
  }
  void join(int u, int v) {
    if (isBlock[u] || isBlock[v]) return;
    u = findRoot(u), v = findRoot(v);
    if (u == v) return;
    if (w[u] < w[v]) swap(u, v);
    par[v] = u;
    w[u] += v;
  }
  int main() {
    scanf("%d %d", &n, &q);
    for (int idx = 0; idx < q; ++idx) {
      scanf("%s %lld %lld", s, &queries[idx].u, &queries[idx].v);
      if (strcmp(s, "ask") == 0)
        queries[idx].queryType = QueryType::ASK;
      else {
        queries[idx].queryType = QueryType::BLOCK;
        curBlockIdx = idx;
        blockRanges.push_back(
            pair<long long, long long>(queries[idx].u, queries[idx].v));
        insert(queries[idx].u, queries[idx].v);
      }
    }
    curBlockIdx = -1;
    sort(blockRanges.begin(), blockRanges.end());
    if (blockRanges[0].first > 0) insert(0, blockRanges[0].first - 1);
    for (int idx = 0; idx < blockRanges.size(); ++idx) {
      if (idx + 1 < blockRanges.size()) {
        if (blockRanges[idx].second + 1 < blockRanges[idx + 1].first)
          insert(blockRanges[idx].second + 1, blockRanges[idx + 1].first - 1);
      } else {
        if (blockRanges[idx].second + 1 < (1LL << n))
          insert(blockRanges[idx].second + 1, (1LL << n) - 1);
      }
    }
    init();
    for (int i = 1; i <= m; ++i) {
      par[i] = i;
      w[i] = 1;
    }
    for (int u = 1; u <= m; ++u)
      for (const int& v : adj[u]) join(u, v);
    vector<Vertex> rootVertices(root->vertices.begin(), root->vertices.end());
    for (int idx = q - 1; idx >= 0; --idx)
      if (queries[idx].queryType == QueryType::ASK) {
        vector<Vertex>::iterator iter = upper_bound(
            rootVertices.begin(), rootVertices.end(),
            Vertex(pair<long long, long long>(queries[idx].u, 1LL << n), m + 1));
        --iter;
        int u = iter->idx;
        iter = upper_bound(
            rootVertices.begin(), rootVertices.end(),
            Vertex(pair<long long, long long>(queries[idx].v, 1LL << n), m + 1));
        --iter;
        int v = iter->idx;
        queries[idx].res = (findRoot(u) == findRoot(v) ? 1 : 0);
      } else {
        for (const int& u : queries[idx].vertexIdx) {
          isBlock[u] = false;
          for (const int& v : adj[u]) join(u, v);
        }
      }
    for (int idx = 0; idx < q; ++idx)
      if (queries[idx].queryType == QueryType::ASK)
        printf("%d\n", queries[idx].res);
    return 0;
  }
  