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 inf = 1e9;
  const long long inf64 = 1e18;
  struct DSU {
    int n = 0;
    vector<int> p, sz;
    DSU() = default;
    DSU(int nn) {
      n = nn;
      p.resize(n);
      iota(p.begin(), p.end(), 0);
      sz.resize(n, 1);
    }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    void merge(int x, int y) {
      x = find(x), y = find(y);
      if (x == y) return;
      if (sz[x] < sz[y]) swap(x, y);
      p[y] = x;
      sz[x] += sz[y];
    }
  };
  struct Query {
    int t = 0;
    long long x = 0;
    long long y = 0;
  };
  vector<int> slow(int n, int m, vector<Query> queries) {
    vector<int> res;
    vector<int> blocked(1 << n);
    for (auto query : queries) {
      if (query.t == 0) {
        for (int i = query.x; i <= query.y; i++) blocked[i] = 1;
      } else {
        vector<int> vis(1 << n);
        vis[query.x] = 1;
        queue<int> q;
        q.push(query.x);
        while (!q.empty()) {
          int v = q.front();
          q.pop();
          for (int i = 0; i < n; i++) {
            int to = v ^ (1 << i);
            if (blocked[to] || vis[to]) continue;
            vis[to] = 1;
            q.push(to);
          }
        }
        res.push_back(vis[query.y]);
      }
    }
    return res;
  }
  vector<int> fast(int n, int m, vector<Query> queries) {
    vector<long long> cuts = {0ll, 1ll << n};
    for (auto query : queries) {
      if (query.t == 0) {
        cuts.push_back(query.x);
        cuts.push_back(query.y + 1);
      }
    }
    sort(cuts.begin(), cuts.end());
    cuts.erase(unique(cuts.begin(), cuts.end()), cuts.end());
    vector<pair<long long, long long>> V;
    vector<vector<int>> g;
    function<void(long long, long long, vector<pair<long long, long long>>)>
        build = [&](long long l, long long r,
                    vector<pair<long long, long long>> segs) {
          if (segs.empty()) {
            return;
          }
          for (auto [ql, qr] : segs) {
            if (ql == l && qr == r) {
              V.emplace_back(l, r);
              g.emplace_back();
              return;
            }
          }
          vector<pair<long long, long long>> lsegs, rsegs;
          long long mid = (l + r) >> 1;
          for (auto [ql, qr] : segs) {
            if (qr <= mid)
              lsegs.emplace_back(ql, qr);
            else if (ql > mid)
              rsegs.emplace_back(ql, qr);
            else {
              lsegs.emplace_back(ql, mid);
              rsegs.emplace_back(mid + 1, qr);
            }
          }
          int sz = (int)V.size();
          build(l, mid, lsegs);
          int ls = (int)V.size() - sz;
          build(mid + 1, r, rsegs);
          int rs = (int)V.size() - sz - ls;
          long long k = (r - l + 1) / 2;
          for (int tl = 0, tr = 0, i = 0; i < ls; i++) {
            while (tr < rs && V[sz + ls + tr].first - k <= V[sz + i].second) tr++;
            while (tl < rs && V[sz + ls + tl].second - k < V[sz + i].first) tl++;
            for (int j = tl; j < tr; j++) {
              int u = sz + i;
              int v = sz + ls + j;
              g[u].push_back(v);
              g[v].push_back(u);
            }
          }
        };
    vector<pair<long long, long long>> segs;
    for (int i = 0; i + 1 < (int)cuts.size(); i++)
      segs.emplace_back(cuts[i], cuts[i + 1] - 1);
    build(0, (1ll << n) - 1, segs);
    vector<vector<int>> to_del(m);
    {
      set<pair<long long, int>> Q;
      for (int i = 0; i < (int)V.size(); i++) Q.insert({V[i].first, i});
      for (int i = 0; i < m; i++) {
        auto query = queries[i];
        if (query.t == 0) {
          for (auto it = Q.lower_bound({query.x, -1});
               it != Q.end() && it->first <= query.y;) {
            to_del[i].push_back(it->second);
            it = Q.erase(it);
          }
        }
      }
    }
    vector<int> blocked(V.size());
    vector<int> res;
    for (int i = 0; i < m; i++) {
      auto query = queries[i];
      if (query.t == 0) {
        for (int v : to_del[i]) blocked[v] = 1;
      } else {
      }
    }
    DSU dsu((int)V.size());
    for (int v = 0; v < (int)V.size(); v++) {
      for (int u : g[v]) {
        if (blocked[u] || blocked[v]) continue;
        dsu.merge(u, v);
      }
    }
    for (int i = m - 1; i >= 0; i--) {
      auto query = queries[i];
      if (query.t == 0) {
        for (int v : to_del[i]) {
          blocked[v] = 0;
        }
        for (int v : to_del[i]) {
          for (int to : g[v]) {
            if (!blocked[to]) dsu.merge(v, to);
          }
        }
      } else {
        int vx = upper_bound(V.begin(), V.end(), make_pair(query.x, inf64)) -
                 V.begin() - 1;
        int vy = upper_bound(V.begin(), V.end(), make_pair(query.y, inf64)) -
                 V.begin() - 1;
        assert(V[vx].first <= query.x && query.x <= V[vx].second);
        assert(V[vy].first <= query.y && query.y <= V[vy].second);
        res.push_back(dsu.find(vx) == dsu.find(vy));
      }
    }
    reverse(res.begin(), res.end());
    return res;
  }
  void test() {
    mt19937 rnd(42);
    const int MAXN = 13;
    const int MAXM = 1e3;
    while (1) {
      int n = rnd() % MAXN + 1;
      int m = rnd() % MAXM + 1;
      vector<Query> queries(m);
      vector<int> blocked(1 << n);
      for (auto& query : queries) {
        vector<int> free;
        for (int v = 0; v < (1 << n); v++) {
          if (!blocked[v]) free.push_back(v);
        }
        if (free.empty()) {
          query.t = 0;
        } else {
          query.t = rnd() % 2;
        }
        if (query.t == 0) {
          query.x = rnd() % (1 << n);
          query.y = rnd() % (1 << n);
          if (query.x > query.y) swap(query.x, query.y);
          for (int i = query.x; i <= query.y; i++) blocked[i] = 1;
        } else {
          query.x = free[rnd() % (int)free.size()];
          query.y = free[rnd() % (int)free.size()];
        }
      }
      vector<int> fs = fast(n, m, queries);
      vector<int> sl = slow(n, m, queries);
      if (fs == sl) {
        cout << "OK( ";
        for (auto x : fs) cout << x << " ";
        cout << ")" << endl;
      } else {
        cout << "WA\n";
        cout << "exp = ";
        for (auto x : sl) cout << x << " ";
        cout << "\n";
        cout << "fnd = ";
        for (auto x : fs) cout << x << " ";
        cout << "\n";
        cout << n << " " << m << "\n";
        vector<string> types = {"block", "ask"};
        for (auto query : queries)
          cout << types[query.t] << " " << query.x << " " << query.y << "\n";
        cout.flush();
        break;
      }
    }
  }
  void work() {
    int n, m;
    cin >> n >> m;
    vector<Query> queries(m);
    for (auto& query : queries) {
      string s;
      cin >> s;
      if (s == "ask")
        query.t = 1;
      else
        query.t = 0;
      cin >> query.x >> query.y;
    }
    vector<int> res = fast(n, m, queries);
    for (auto x : res) cout << x << "\n";
  }
  int main() {
    work();
    return 0;
  }
  