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 IINF = 0x3f3f3f3f;
  const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
  const double DINF = numeric_limits<double>::infinity();
  const double DNAN = numeric_limits<double>::quiet_NaN();
  const double EPS = 1e-9;
  const double PI = acos((double)-1.0);
  const int DX[] = {1, 0, -1, 0, 1, -1, 1, -1};
  const int DY[] = {0, 1, 0, -1, 1, -1, -1, 1};
  long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
  long long sqr(long long x) { return x * x; }
  long long sqr(int x) { return (long long)x * x; }
  double sqr(double x) { return x * x; }
  mt19937 mmtw(960172);
  long long rnd(long long x, long long y) {
    static uniform_int_distribution<long long> d;
    return d(mmtw) % (y - x + 1) + x;
  }
  template <typename T>
  T& updMin(T& a, T const& b) {
    if (b < a) a = b;
    return a;
  }
  template <typename T>
  T& updMax(T& a, T const& b) {
    if (a < b) a = b;
    return a;
  }
  long long divFloor(long long a, long long b) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
    return a >= 0 ? a / b : (a - b + 1) / b;
  }
  long long divCeil(long long a, long long b) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
    return a >= 0 ? (a + b - 1) / b : a / b;
  }
  long long divFloorS(long long a, long long b) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
    return a >= 0 ? (a + b - 1) / b - 1 : a / b - 1;
  }
  long long divCeilS(long long a, long long b) {
    if (b < 0) {
      a = -a;
      b = -b;
    }
    return a >= 0 ? a / b + 1 : (a - b + 1) / b + 1;
  }
  template <typename K, typename V>
  V getOrDef(map<K, V> const& a, K const& k, V const& def = V()) {
    auto it = a.find(k);
    return it == a.end() ? def : it->second;
  }
  template <typename K, typename V>
  V getOrDef(unordered_map<K, V> const& a, K const& k, V const& def = V()) {
    auto it = a.find(k);
    return it == a.end() ? def : it->second;
  }
  template <typename A, typename B>
  istream& operator>>(istream& in, pair<A, B>& p) {
    return in >> p.first >> p.second;
  }
  template <typename A, typename B>
  ostream& operator<<(ostream& out, pair<A, B> const& p) {
    return out << p.first << " " << p.second;
  }
  template <typename T>
  istream& operator>>(istream& in, vector<T>& a) {
    for (T& x : a) in >> x;
    return in;
  }
  template <typename T>
  ostream& operator<<(ostream& out, vector<T> const& a) {
    bool f = true;
    for (T const& x : a) {
      if (!f) out << " ";
      f = false;
      out << x;
    }
    return out;
  }
  template <typename T>
  bool isZero(T const& x) {
    return x == T(0);
  }
  bool isZero(float x) { return abs(x) < EPS; }
  bool isZero(double x) { return abs(x) < EPS; }
  bool isZero(long double x) { return abs(x) < EPS; }
  template <typename T>
  int sgn(T const& x) {
    if (isZero(x)) return 0;
    return x > 0 ? 1 : -1;
  }
  struct Node {
    long long cl, cr;
    Node* l = nullptr;
    Node* r = nullptr;
    int id = -1;
    bool leaf = true;
    bool destroyed = 0;
    Node(long long cl, long long cr) : cl(cl), cr(cr) {}
  };
  struct Query {
    bool destroy;
    long long a, b;
  };
  void down1(long long l, long long r, Node* c) {
    if (l >= c->cr || c->cl >= r) return;
    if (l <= c->cl && c->cr <= r) {
      assert(c->leaf);
      c->destroyed = 1;
      return;
    }
    if (c->leaf) {
      assert(!c->destroyed);
      c->leaf = 0;
      long long mid = (c->cl + c->cr) / 2;
      c->l = new Node(c->cl, mid);
      c->r = new Node(mid, c->cr);
    }
    down1(l, r, c->l);
    down1(l, r, c->r);
  }
  vector<Node*> leafs;
  vector<long long> cls;
  void dfs2(Node* c) {
    if (c->leaf) {
      leafs.push_back(c);
      cls.push_back(c->cl);
    } else {
      dfs2(c->l);
      dfs2(c->r);
    }
  }
  struct DSU {
    vector<int> p;
    DSU() = default;
    DSU(int n) : p(n, -1) {}
    int get(int v) { return p[v] == -1 ? v : p[v] = get(p[v]); }
    bool merge(int x, int y) {
      x = get(x);
      y = get(y);
      if (x == y) return false;
      p[y] = x;
      return true;
    }
  } dsu;
  int k;
  Node* root;
  int main() {
    ios::sync_with_stdio(false);
    int qn;
    cin >> k >> qn;
    long long n = 1LL << k;
    vector<Query> qs;
    root = new Node(0, n);
    for (int i = 0; i < qn; ++i) {
      string type;
      long long a, b;
      cin >> type >> a >> b;
      if (type == "block") {
        qs.push_back({1, a, b + 1});
        down1(a, b + 1, root);
      } else {
        qs.push_back({0, a, b});
      }
    }
    dfs2(root);
    for (int i = 0; i < ((int)((leafs).size())); ++i) leafs[i]->id = i;
    dsu = DSU(((int)((leafs).size())));
    for (int id = 0; id < ((int)((leafs).size())); ++id) {
      Node* c = leafs[id];
      if (c->destroyed) continue;
      long long len = c->cr - c->cl;
      for (int i = 0; i < k; ++i) {
        if ((1LL << i) < len) continue;
        long long nl = c->cl ^ (1LL << i);
        long long nr = nl + len;
        int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
        while (j < ((int)((cls).size())) && cls[j] < nr) {
          if (!leafs[j]->destroyed) dsu.merge(id, j);
          j++;
        }
      }
    }
    vector<int> ans;
    reverse((qs).begin(), (qs).end());
    for (Query const& q : qs) {
      if (q.destroy) {
        int id1 = lower_bound((cls).begin(), (cls).end(), q.a) - cls.begin();
        int id2 = lower_bound((cls).begin(), (cls).end(), q.b) - cls.begin();
        for (int id = id1; id < id2; ++id) {
          Node* c = leafs[id];
          c->destroyed = false;
          long long len = c->cr - c->cl;
          for (int i = 0; i < k; ++i) {
            if ((1LL << i) < len) continue;
            long long nl = c->cl ^ (1LL << i);
            long long nr = nl + len;
            int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
            while (j < ((int)((cls).size())) && cls[j] < nr) {
              if (!leafs[j]->destroyed) dsu.merge(id, j);
              j++;
            }
          }
        }
      } else {
        int id1 = upper_bound((cls).begin(), (cls).end(), q.a) - cls.begin() - 1;
        int id2 = upper_bound((cls).begin(), (cls).end(), q.b) - cls.begin() - 1;
        ans.push_back(dsu.get(id1) == dsu.get(id2));
      }
    }
    reverse((ans).begin(), (ans).end());
    for (int x : ans) cout << x << "\n";
    return 0;
  }
  