#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;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

<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.

### Response

```cpp
#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;
}

```