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;
  #pragma GCC optimize("Ofast,unroll-loops")
  #pragma GCC target("avx,avx2,sse,sse2")
  template <class c>
  struct rge {
    c b, e;
  };
  template <class c>
  rge<c> range(c i, c j) {
    return rge<c>{i, j};
  }
  template <class c>
  auto dud(c *x) -> decltype(cerr << *x, 0);
  template <class c>
  char dud(...);
  struct debug {
    template <class c>
    debug &operator<<(const c &) {
      return *this;
    }
  };
  struct segment {
    long long a, b;
    int t;
    int id;
    segment(long long _a = 0, long long _b = 0, int _t = 0, int _id = 0) {
      a = _a;
      b = _b;
      t = _t;
      id = _id;
    }
  };
  struct query {
    long long a, b;
    int t;
    query(long long _a = 0, long long _b = 0, int _t = 0) {
      a = _a;
      b = _b;
      t = _t;
    }
  };
  const int MAXN = 51;
  const int MAXM = 5e4 + 10;
  vector<segment> segments;
  vector<query> queries;
  vector<int> gr[2 * MAXN * MAXM];
  int t[2 * MAXN * MAXM];
  int card[2 * MAXN * MAXM];
  int no = 0;
  vector<segment> rec(long long l, long long r, vector<segment> &segments) {
    vector<segment> s;
    if (!segments.size()) {
      s.emplace_back(l, r, 1e9, no++);
      return s;
    }
    if (segments.size() == 1 && segments[0].a == l && segments[0].b == r) {
      s.emplace_back(l, r, segments[0].t, no++);
      return s;
    }
    vector<segment> s_left;
    vector<segment> s_right;
    long long m = l + r >> 1;
    for (auto &x : segments) {
      if (x.b <= m) {
        s_left.emplace_back(x);
      } else if (x.a > m) {
        s_right.emplace_back(x);
      } else {
        s_left.emplace_back(x.a, m, x.t);
        s_right.emplace_back(m + 1, x.b, x.t);
      }
    }
    auto ss_left = rec(l, m, s_left);
    auto ss_right = rec(m + 1, r, s_right);
    int long long = 0, rr = 0;
    long long dif = m + 1 - l;
    while (long long < ss_left.size() && rr < ss_right.size()) {
      if ((ss_left[long long].a >= ss_right[rr].a - dif &&
           ss_left[long long].a <= ss_right[rr].b - dif) ||
          (ss_right[rr].a >= ss_left[long long].a + dif &&
           ss_right[rr].a <= ss_left[long long].b + dif)) {
        gr[ss_left[long long].id].emplace_back(ss_right[rr].id);
        gr[ss_right[rr].id].emplace_back(ss_left[long long].id);
      }
      if (ss_left[long long].b <= ss_right[rr].b - dif) {
        ++long long;
      } else {
        ++rr;
      }
    }
    for (auto &x : ss_right) {
      ss_left.emplace_back(x);
    }
    return ss_left;
  }
  int root(int x) { return x == t[x] ? x : t[x] = root(t[x]); }
  void onion(int x, int y) {
    if ((x = root(x)) == (y = root(y))) return;
    if (card[x] < card[y]) swap(x, y);
    t[y] = x;
    card[x] += card[y];
    return;
  };
  int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
      string s;
      long long a, b;
      cin >> s >> a >> b;
      if (s == "ask") {
        queries.emplace_back(a, b, i);
      } else {
        segments.emplace_back(a, b, i, segments.size());
      }
    }
    auto s = rec(0, (1ll << n) - 1, segments);
    for (int i = 0; i < no; ++i) {
      t[i] = i;
      card[i] = 1;
    }
    reverse((queries).begin(), (queries).end());
    vector<int> alive(no);
    auto s_time = s;
    sort((s_time).begin(), (s_time).end(),
         [&](segment &a, segment &b) { return a.t > b.t; });
    auto getSegment = [&](long long a) {
      int ret = 0;
      int l = 0, r = s.size() - 1;
      while (l <= r) {
        int m = l + r >> 1;
        if (s[m].a <= a && s[m].b >= a) return s[m].id;
        if (s[m].b < a) {
          l = m + 1;
        } else {
          r = m - 1;
        }
      }
      assert(false);
      return -1;
    };
    int now = 0;
    vector<int> ans;
    for (auto &x : queries) {
      while (now < s_time.size() && s_time[now].t >= x.t) {
        alive[s_time[now].id] = 1;
        for (auto &x : gr[s_time[now].id]) {
          if (alive[x]) onion(root(s_time[now].id), root(x));
        }
        ++now;
      }
      ans.emplace_back(root(getSegment(x.a)) == root(getSegment(x.b)));
    }
    reverse((ans).begin(), (ans).end());
    for (auto &x : ans) cout << x << '\n';
    return 0;
  }
  