#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
long long l[maxn], r[maxn];
int op[maxn], root, id[maxn * 100], tot, idtot, ls[maxn * 100], rs[maxn * 100],
    ban[maxn * 100], fa[maxn * 100], n;
vector<int> has[maxn], g[maxn * 100];
void add(int &rt, long long l, long long r, long long ql, long long qr) {
  if (!rt) rt = ++tot;
  if (l >= ql && r <= qr) {
    id[rt] = ++idtot;
    return;
  }
  long long mid = l + r >> 1;
  if (ql <= mid) add(ls[rt], l, mid, ql, qr);
  if (qr >= mid + 1) add(rs[rt], mid + 1, r, ql, qr);
}
void getedge(int L, int R, int cur, int limt) {
  if (!L || !R) return;
  if (cur > limt) {
    getedge(ls[L], ls[R], cur - 1, limt);
    getedge(rs[L], rs[R], cur - 1, limt);
    return;
  }
  if (cur == limt) {
    getedge(ls[L], rs[R], cur - 1, limt);
    return;
  }
  if (id[L] && id[R]) {
    g[id[L]].push_back(id[R]);
    g[id[R]].push_back(id[L]);
    return;
  }
  if (id[L]) {
    getedge(L, ls[R], cur - 1, limt);
    getedge(L, rs[R], cur - 1, limt);
    return;
  }
  if (id[R]) {
    getedge(ls[L], R, cur - 1, limt);
    getedge(rs[L], R, cur - 1, limt);
    return;
  }
  getedge(ls[L], ls[R], cur - 1, limt);
  getedge(rs[L], rs[R], cur - 1, limt);
}
void getpoint(int rt, long long l, long long r, int i, long long ql,
              long long qr) {
  if (l >= ql && r <= qr) {
    has[i].push_back(id[rt]);
    ban[id[rt]] = 1;
    return;
  }
  long long mid = l + r >> 1;
  if (ql <= mid) getpoint(ls[rt], l, mid, i, ql, qr);
  if (qr >= mid + 1) getpoint(rs[rt], mid + 1, r, i, ql, qr);
}
int fd(int rt) { return rt == fa[rt] ? rt : (fa[rt] = fd(fa[rt])); }
void merge(int u, int v) {
  if (fd(u) == fd(v)) return;
  fa[fd(u)] = fd(v);
}
void insert(int x) {
  fa[x] = x;
  for (auto u : g[x]) {
    if (fa[u]) merge(x, u);
  }
}
int getbl(long long x) {
  int u = root;
  if (id[u]) return id[u];
  for (int i = n - 1; i >= 0; --i) {
    if ((x >> i) & 1) {
      u = rs[u];
    } else
      u = ls[u];
    if (id[u]) return id[u];
  }
}
int main() {
  int m;
  vector<long long> x;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    char s[5];
    scanf("%s%lld%lld", s, l + i, r + i);
    if (s[0] == 'b') {
      x.push_back(l[i] - 1);
      x.push_back(r[i]);
    } else
      op[i] = 1;
  }
  long long mx = (1ll << n) - 1;
  x.push_back(-1);
  x.push_back(mx);
  sort(x.begin(), x.end());
  x.resize(unique(x.begin(), x.end()) - x.begin());
  for (int i = 1; i < x.size(); ++i) add(root, 0, mx, x[i - 1] + 1, x[i]);
  for (int i = 0; i < n; ++i) getedge(root, root, n - 1, i);
  for (int i = 0; i < m; ++i)
    if (!op[i]) getpoint(root, 0, mx, i, l[i], r[i]);
  for (int i = 1; i <= idtot; ++i)
    if (!ban[i]) insert(i);
  vector<int> ans;
  for (int i = m - 1; i >= 0; --i) {
    l[i] = getbl(l[i]), r[i] = getbl(r[i]);
    if (op[i]) {
      ans.push_back(fd(l[i]) == fd(r[i]));
    } else {
      for (auto u : has[i]) {
        insert(u);
      }
    }
  }
  for (int i = (int)ans.size() - 1; i >= 0; --i) printf("%d\n", ans[i]);
}

### Prompt

Develop a solution in Cpp to the problem described below:

<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 maxn = 5e4 + 5;
long long l[maxn], r[maxn];
int op[maxn], root, id[maxn * 100], tot, idtot, ls[maxn * 100], rs[maxn * 100],
    ban[maxn * 100], fa[maxn * 100], n;
vector<int> has[maxn], g[maxn * 100];
void add(int &rt, long long l, long long r, long long ql, long long qr) {
  if (!rt) rt = ++tot;
  if (l >= ql && r <= qr) {
    id[rt] = ++idtot;
    return;
  }
  long long mid = l + r >> 1;
  if (ql <= mid) add(ls[rt], l, mid, ql, qr);
  if (qr >= mid + 1) add(rs[rt], mid + 1, r, ql, qr);
}
void getedge(int L, int R, int cur, int limt) {
  if (!L || !R) return;
  if (cur > limt) {
    getedge(ls[L], ls[R], cur - 1, limt);
    getedge(rs[L], rs[R], cur - 1, limt);
    return;
  }
  if (cur == limt) {
    getedge(ls[L], rs[R], cur - 1, limt);
    return;
  }
  if (id[L] && id[R]) {
    g[id[L]].push_back(id[R]);
    g[id[R]].push_back(id[L]);
    return;
  }
  if (id[L]) {
    getedge(L, ls[R], cur - 1, limt);
    getedge(L, rs[R], cur - 1, limt);
    return;
  }
  if (id[R]) {
    getedge(ls[L], R, cur - 1, limt);
    getedge(rs[L], R, cur - 1, limt);
    return;
  }
  getedge(ls[L], ls[R], cur - 1, limt);
  getedge(rs[L], rs[R], cur - 1, limt);
}
void getpoint(int rt, long long l, long long r, int i, long long ql,
              long long qr) {
  if (l >= ql && r <= qr) {
    has[i].push_back(id[rt]);
    ban[id[rt]] = 1;
    return;
  }
  long long mid = l + r >> 1;
  if (ql <= mid) getpoint(ls[rt], l, mid, i, ql, qr);
  if (qr >= mid + 1) getpoint(rs[rt], mid + 1, r, i, ql, qr);
}
int fd(int rt) { return rt == fa[rt] ? rt : (fa[rt] = fd(fa[rt])); }
void merge(int u, int v) {
  if (fd(u) == fd(v)) return;
  fa[fd(u)] = fd(v);
}
void insert(int x) {
  fa[x] = x;
  for (auto u : g[x]) {
    if (fa[u]) merge(x, u);
  }
}
int getbl(long long x) {
  int u = root;
  if (id[u]) return id[u];
  for (int i = n - 1; i >= 0; --i) {
    if ((x >> i) & 1) {
      u = rs[u];
    } else
      u = ls[u];
    if (id[u]) return id[u];
  }
}
int main() {
  int m;
  vector<long long> x;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    char s[5];
    scanf("%s%lld%lld", s, l + i, r + i);
    if (s[0] == 'b') {
      x.push_back(l[i] - 1);
      x.push_back(r[i]);
    } else
      op[i] = 1;
  }
  long long mx = (1ll << n) - 1;
  x.push_back(-1);
  x.push_back(mx);
  sort(x.begin(), x.end());
  x.resize(unique(x.begin(), x.end()) - x.begin());
  for (int i = 1; i < x.size(); ++i) add(root, 0, mx, x[i - 1] + 1, x[i]);
  for (int i = 0; i < n; ++i) getedge(root, root, n - 1, i);
  for (int i = 0; i < m; ++i)
    if (!op[i]) getpoint(root, 0, mx, i, l[i], r[i]);
  for (int i = 1; i <= idtot; ++i)
    if (!ban[i]) insert(i);
  vector<int> ans;
  for (int i = m - 1; i >= 0; --i) {
    l[i] = getbl(l[i]), r[i] = getbl(r[i]);
    if (op[i]) {
      ans.push_back(fd(l[i]) == fd(r[i]));
    } else {
      for (auto u : has[i]) {
        insert(u);
      }
    }
  }
  for (int i = (int)ans.size() - 1; i >= 0; --i) printf("%d\n", ans[i]);
}

```