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;
  void per() { cerr << endl; }
  template <typename Head, typename... Tail>
  void per(Head H, Tail... T) {
    cerr << H << ' ';
    per(T...);
  }
  template <class T>
  bool uin(T& a, T b) {
    return a > b ? (a = b, true) : false;
  }
  template <class T>
  bool uax(T& a, T b) {
    return a < b ? (a = b, true) : false;
  }
  template <class U, class V>
  ostream& operator<<(ostream& out, const pair<U, V>& a) {
    return out << "(" << a.first << ", " << a.second << ")";
  }
  template <class U, class V>
  istream& operator>>(istream& in, pair<U, V>& a) {
    return in >> a.first >> a.second;
  }
  template <typename W,
            typename T = typename enable_if<!is_same<W, string>::value,
                                            typename W::value_type>::type>
  ostream& operator<<(ostream& out, const W& v) {
    out << "{ ";
    for (const auto& first : v) out << first << ", ";
    return out << '}';
  }
  template <class T>
  void readArr(T from, T to) {
    for (auto i = from; i != to; ++i) cin >> *i;
  }
  mt19937 mrand(1337);
  unsigned int myRand32() { return mrand() & (unsigned int)(-1); }
  unsigned long long myRand64() {
    return ((unsigned long long)myRand32() << 32) ^ myRand32();
  }
  const int mod = 1000000007;
  void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
  }
  void dec(int& a, int b) {
    a -= b;
    if (a < 0) a += mod;
  }
  int mult(int a, int b) { return a * (long long)b % mod; }
  int bp(int a, int b) {
    int res = 1;
    while (b > 0) {
      if (b & 1) res = mult(res, a);
      a = mult(a, a);
      b >>= 1;
    }
    return res;
  }
  struct Vertex {
    int l;
    int r;
    int father;
    int cnt;
  };
  Vertex rmq[4000007];
  int ptr = 0;
  vector<int> want[4000007];
  int create(int vertex) {
    rmq[ptr++] = {-1, -1, vertex, 0};
    want[ptr - 1] = {};
    return ptr - 1;
  }
  void go(int vertex, long long l, long long r, long long l1, long long r1) {
    if (l1 >= r1) return;
    if (l == l1 && r == r1) {
      rmq[vertex].cnt = 1;
      return;
    }
    if (rmq[vertex].l == -1) {
      rmq[vertex].l = create(vertex);
    }
    if (rmq[vertex].r == -1) {
      rmq[vertex].r = create(vertex);
    }
    long long mid = (l + r) / 2;
    go(rmq[vertex].l, l, mid, l1, min(r1, mid));
    go(rmq[vertex].r, mid, r, max(l1, mid), r1);
    rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
  }
  struct Node {
    int p, r, f;
  };
  struct DSU {
    static const int SZ = 10000007;
    Node t[SZ];
    DSU() { reset(SZ); }
    void reset(int n) {
      for (int i = 0; i < n; ++i) {
        t[i].p = i;
        t[i].r = 0;
        t[i].f = 1;
      }
    }
    int get(int v) {
      if (t[v].p == v) return v;
      return t[v].p = get(t[v].p);
    }
    int get_func(int v) { return t[get(v)].f; }
    void merge(int a, int b) {
      a = get(a), b = get(b);
      if (a != b) {
        if (t[a].r < t[b].r) swap(a, b);
        t[b].p = a;
        t[a].f += t[b].f;
        if (t[a].r == t[b].r) ++t[a].r;
      }
    }
  };
  DSU dsu;
  bool good(int vertex) {
    if (vertex == -1) return false;
    if (rmq[vertex].cnt) return false;
    return true;
  }
  void restore(int vertex) {
    if (good(rmq[vertex].father)) dsu.merge(vertex, rmq[vertex].father);
    if (good(rmq[vertex].l)) dsu.merge(vertex, rmq[vertex].l);
    if (good(rmq[vertex].r)) dsu.merge(vertex, rmq[vertex].r);
    for (auto to : want[vertex]) dsu.merge(vertex, to);
    int W = vertex;
    vector<int> bits;
    while (true) {
      int t = rmq[vertex].father;
      if (t == -1) break;
      if (rmq[t].l == vertex)
        bits.push_back(0);
      else
        bits.push_back(1);
      vertex = t;
    }
    reverse(bits.begin(), bits.end());
    int start = 0;
    for (int i = 0; i < bits.size() && start != -1; ++i) {
      bits[i] ^= 1;
      int now = start;
      for (int j = i; j < bits.size(); ++j) {
        int first = bits[j];
        if (first == 0) {
          if (rmq[now].l == -1) {
            break;
          }
          now = rmq[now].l;
        } else {
          if (rmq[now].r == -1) {
            break;
          }
          now = rmq[now].r;
        }
      }
      if (good(now)) {
        dsu.merge(W, now);
      } else
        want[now].push_back(W);
      bits[i] ^= 1;
      if (bits[i] == 0) start = rmq[start].l;
      if (bits[i] == 1) start = rmq[start].r;
    }
  }
  void go_back(int vertex, long long l, long long r, long long l1, long long r1) {
    if (l1 >= r1) return;
    if (l == l1 && r == r1) {
      rmq[vertex].cnt = 0;
      restore(vertex);
      return;
    }
    long long mid = (l + r) / 2;
    go_back(rmq[vertex].l, l, mid, l1, min(r1, mid));
    go_back(rmq[vertex].r, mid, r, max(l1, mid), r1);
    int W = rmq[vertex].cnt;
    rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
    if (rmq[vertex].cnt == 0 && W != 0) restore(vertex);
  }
  int n, m;
  int gg(long long first) {
    int now = 0;
    for (int i = n - 1; i >= 0; --i) {
      int t = (((1LL << i) & first) > 0);
      if (t == 0) {
        if (rmq[now].l == -1) return now;
        now = rmq[now].l;
      } else {
        if (rmq[now].r == -1) return now;
        now = rmq[now].r;
      }
    }
    return now;
  }
  int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    create(-1);
    rmq[0].l = create(0);
    rmq[0].r = create(0);
    vector<tuple<int, long long, long long> > queries;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
      string s;
      cin >> s;
      if (s == "ask") {
        long long l, r;
        cin >> l >> r;
        queries.push_back(make_tuple(0, l, r));
      } else {
        long long l, r;
        cin >> l >> r;
        queries.push_back(make_tuple(1, l, r));
        go(0, 0, (1ll << n), l, r + 1);
      }
    }
    vector<int> ans;
    dsu.reset(ptr);
    for (int i = 0; i < ptr; ++i) {
      if (!rmq[i].cnt) {
        restore(i);
      }
    }
    reverse(queries.begin(), queries.end());
    for (auto first : queries) {
      int tp = get<0>(first);
      long long l = get<1>(first);
      long long r = get<2>(first);
      if (tp == 1) {
        go_back(0, 0, (1ll << n), l, r + 1);
      } else {
        int A = gg(l), B = gg(r);
        if (dsu.get(A) == dsu.get(B) && !rmq[A].cnt && !rmq[B].cnt)
          ans.push_back(1);
        else
          ans.push_back(0);
      }
    }
    reverse(ans.begin(), ans.end());
    for (auto first : ans) cout << first << '\n';
  }
  