#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9, MOD = 1e9 + 7;
template <class A, class B>
pair<A, B> operator+(pair<A, B>& a, pair<A, B>& b) {
  return {a.first + b.first, a.second + b.second};
}
template <class A, class B>
pair<A, B> operator-(pair<A, B>& a, pair<A, B>& b) {
  return {a.first - b.first, a.second - b.second};
}
template <class A, class B>
istream& operator>>(istream& is, pair<A, B>& a) {
  return is >> a.first >> a.second;
}
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& a) {
  return os << "< " << a.first << " , " << a.second << " >";
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << '[';
  if (!v.empty()) {
    os << v[0];
    for (int i = (1); i < (v.size()); i++) os << ',' << v[i];
  }
  return os << ']';
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
  os << '{';
  if (!v.empty()) {
    os << *v.begin();
    for (auto it = ++v.begin(); it != v.end(); ++it) os << ',' << *it;
  }
  return os << '}';
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto DIST = uniform_int_distribution<int>(0, INF);
struct DSU {
  vector<int> p, sz;
  DSU(int n) : p(n, -1), sz(n, 1) {}
  int find(int c) {
    if (p[c] == -1) return c;
    return p[c] = find(p[c]);
  }
  bool uni(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return 0;
    if (sz[a] > sz[b]) swap(a, b);
    p[a] = b, sz[b] += sz[a];
    return 1;
  }
};
const int MAX = 2e6;
int sz;
int t[MAX];
long long rr[MAX];
vector<int> g[MAX];
pair<pair<long long, long long>, int> segs[MAX];
int solve(int lseg, int rseg, long long l, long long r) {
  if (lseg == rseg) {
    if (sz >= MAX) exit(1);
    t[sz] = INF, rr[sz] = r, g[sz] = vector<int>(0);
    sz++;
    return 1;
  }
  if (rseg - lseg == 1 && segs[lseg].first.first <= l &&
      segs[lseg].first.second >= r) {
    if (sz >= MAX) exit(1);
    t[sz] = segs[lseg].second, rr[sz] = r, g[sz] = vector<int>(0);
    sz++;
    return 1;
  }
  long long mid = (l + r + 1) / 2;
  int nr = lseg;
  while (nr < rseg && segs[nr].first.first < mid) nr++;
  int befl = sz;
  int lsz = solve(lseg, nr, l, mid - 1);
  int nl = rseg;
  while (nl > lseg && segs[nl - 1].first.second >= mid) nl--;
  int befr = sz;
  int rsz = solve(nl, rseg, mid, r);
  int i = befl, j = befr;
  while (i < befl + lsz && j < befr + rsz) {
    g[i].push_back(j), g[j].push_back(i);
    if (rr[i] - l == rr[j] - mid)
      i++, j++;
    else if (rr[i] - l < rr[j] - mid)
      i++;
    else
      j++;
  }
  return lsz + rsz;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<pair<pair<long long, long long>, int>> qur;
  int segsz = 0;
  for (int i = (0); i < (q); i++) {
    string s;
    cin >> s;
    long long a, b;
    cin >> a >> b;
    if (s == "ask") {
      qur.push_back({{a, b}, i});
    } else {
      segs[segsz++] = {{a, b}, i};
    }
  }
  sort(segs, segs + segsz);
  long long N = long long(1) << n;
  solve(0, segsz, 0, N - 1);
  vector<vector<int>> hist(q + 1);
  for (int i = (0); i < (sz); i++) {
    if (t[i] == INF)
      hist[q].push_back(i);
    else
      hist[t[i]].push_back(i);
  }
  vector<pair<int, int>> ord;
  for (int first = (q + 1) - 1; first >= (0); first--)
    for (int i : hist[first]) ord.push_back({first, i});
  DSU dsu(sz);
  reverse(qur.begin(), qur.end());
  vector<int> ans;
  int i = 0;
  for (auto qq : qur) {
    while (i < sz && ord[i].first > qq.second) {
      int cur = ord[i].second;
      for (auto nei : g[cur])
        if (t[nei] >= t[cur]) {
          dsu.uni(cur, nei);
        }
      i++;
    }
    long long a = qq.first.first, b = qq.first.second;
    int aa = lower_bound(rr, rr + sz, a) - rr;
    int bb = lower_bound(rr, rr + sz, b) - rr;
    ans.push_back(dsu.find(aa) == dsu.find(bb));
  }
  reverse(ans.begin(), ans.end());
  for (int first : ans) cout << first << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

<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, MOD = 1e9 + 7;
template <class A, class B>
pair<A, B> operator+(pair<A, B>& a, pair<A, B>& b) {
  return {a.first + b.first, a.second + b.second};
}
template <class A, class B>
pair<A, B> operator-(pair<A, B>& a, pair<A, B>& b) {
  return {a.first - b.first, a.second - b.second};
}
template <class A, class B>
istream& operator>>(istream& is, pair<A, B>& a) {
  return is >> a.first >> a.second;
}
template <class A, class B>
ostream& operator<<(ostream& os, const pair<A, B>& a) {
  return os << "< " << a.first << " , " << a.second << " >";
}
template <class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << '[';
  if (!v.empty()) {
    os << v[0];
    for (int i = (1); i < (v.size()); i++) os << ',' << v[i];
  }
  return os << ']';
}
template <class T>
ostream& operator<<(ostream& os, set<T> v) {
  os << '{';
  if (!v.empty()) {
    os << *v.begin();
    for (auto it = ++v.begin(); it != v.end(); ++it) os << ',' << *it;
  }
  return os << '}';
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto DIST = uniform_int_distribution<int>(0, INF);
struct DSU {
  vector<int> p, sz;
  DSU(int n) : p(n, -1), sz(n, 1) {}
  int find(int c) {
    if (p[c] == -1) return c;
    return p[c] = find(p[c]);
  }
  bool uni(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return 0;
    if (sz[a] > sz[b]) swap(a, b);
    p[a] = b, sz[b] += sz[a];
    return 1;
  }
};
const int MAX = 2e6;
int sz;
int t[MAX];
long long rr[MAX];
vector<int> g[MAX];
pair<pair<long long, long long>, int> segs[MAX];
int solve(int lseg, int rseg, long long l, long long r) {
  if (lseg == rseg) {
    if (sz >= MAX) exit(1);
    t[sz] = INF, rr[sz] = r, g[sz] = vector<int>(0);
    sz++;
    return 1;
  }
  if (rseg - lseg == 1 && segs[lseg].first.first <= l &&
      segs[lseg].first.second >= r) {
    if (sz >= MAX) exit(1);
    t[sz] = segs[lseg].second, rr[sz] = r, g[sz] = vector<int>(0);
    sz++;
    return 1;
  }
  long long mid = (l + r + 1) / 2;
  int nr = lseg;
  while (nr < rseg && segs[nr].first.first < mid) nr++;
  int befl = sz;
  int lsz = solve(lseg, nr, l, mid - 1);
  int nl = rseg;
  while (nl > lseg && segs[nl - 1].first.second >= mid) nl--;
  int befr = sz;
  int rsz = solve(nl, rseg, mid, r);
  int i = befl, j = befr;
  while (i < befl + lsz && j < befr + rsz) {
    g[i].push_back(j), g[j].push_back(i);
    if (rr[i] - l == rr[j] - mid)
      i++, j++;
    else if (rr[i] - l < rr[j] - mid)
      i++;
    else
      j++;
  }
  return lsz + rsz;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<pair<pair<long long, long long>, int>> qur;
  int segsz = 0;
  for (int i = (0); i < (q); i++) {
    string s;
    cin >> s;
    long long a, b;
    cin >> a >> b;
    if (s == "ask") {
      qur.push_back({{a, b}, i});
    } else {
      segs[segsz++] = {{a, b}, i};
    }
  }
  sort(segs, segs + segsz);
  long long N = long long(1) << n;
  solve(0, segsz, 0, N - 1);
  vector<vector<int>> hist(q + 1);
  for (int i = (0); i < (sz); i++) {
    if (t[i] == INF)
      hist[q].push_back(i);
    else
      hist[t[i]].push_back(i);
  }
  vector<pair<int, int>> ord;
  for (int first = (q + 1) - 1; first >= (0); first--)
    for (int i : hist[first]) ord.push_back({first, i});
  DSU dsu(sz);
  reverse(qur.begin(), qur.end());
  vector<int> ans;
  int i = 0;
  for (auto qq : qur) {
    while (i < sz && ord[i].first > qq.second) {
      int cur = ord[i].second;
      for (auto nei : g[cur])
        if (t[nei] >= t[cur]) {
          dsu.uni(cur, nei);
        }
      i++;
    }
    long long a = qq.first.first, b = qq.first.second;
    int aa = lower_bound(rr, rr + sz, a) - rr;
    int bb = lower_bound(rr, rr + sz, b) - rr;
    ans.push_back(dsu.find(aa) == dsu.find(bb));
  }
  reverse(ans.begin(), ans.end());
  for (int first : ans) cout << first << endl;
  return 0;
}

```