#include <bits/stdc++.h>
using namespace std;
const int M = 55555;
const int W = M * 100;
int n, m, qt[M], ans[M];
long long o, ql[M], qr[M];
vector<long long> v;
int tot, cnt, ls[W], rs[W], a[W], rt, p[W];
vector<int> e[W], g[M];
void modify(int& k, long long L, long long R, long long l = 0,
            long long r = o - 1) {
  if (!k) k = ++tot;
  if (L <= l && r <= R) {
    a[k] = ++cnt;
    return;
  }
  long long h = l + r >> 1;
  if (L <= h) modify(ls[k], L, R, l, h);
  if (h < R) modify(rs[k], L, R, h + 1, r);
}
void dfs(int k1, int k2, int d, int D) {
  if (d > D) {
    if (a[k1]) return;
    dfs(ls[k1], ls[k2], d - 1, D);
    dfs(rs[k1], rs[k2], d - 1, D);
    return;
  }
  if (d == D) {
    if (a[k1]) return;
    dfs(ls[k1], rs[k2], d - 1, D);
    return;
  }
  if (a[k1] && a[k2]) {
    e[a[k1]].push_back(a[k2]);
    e[a[k2]].push_back(a[k1]);
    return;
  }
  if (a[k1]) {
    dfs(k1, ls[k2], d - 1, D);
    dfs(k1, rs[k2], d - 1, D);
    return;
  }
  if (a[k2]) {
    dfs(ls[k1], k2, d - 1, D);
    dfs(rs[k1], k2, d - 1, D);
    return;
  }
  dfs(ls[k1], ls[k2], d - 1, D);
  dfs(rs[k1], rs[k2], d - 1, D);
}
void query(int k, long long L, long long R, int i, long long l = 0,
           long long r = o - 1) {
  if (L <= l && r <= R) {
    p[a[k]] = i;
    g[i].push_back(a[k]);
    return;
  }
  long long h = l + r >> 1;
  if (L <= h) query(ls[k], L, R, i, l, h);
  if (h < R) query(rs[k], L, R, i, h + 1, r);
}
int f[W];
int fnd(int x) {
  if (f[x] == x) return x;
  return f[x] = fnd(f[x]);
}
void ins(int x) {
  int i;
  f[x] = x;
  for (i = 0; i < e[x].size(); i++)
    if (f[e[x][i]]) f[fnd(x)] = fnd(e[x][i]);
}
int geta(int k, long long x) {
  int i;
  for (i = n - 1; i >= 0; i--) {
    if ((x >> i) & 1)
      k = rs[k];
    else
      k = ls[k];
    if (a[k]) return a[k];
  }
}
int main() {
  int i, j;
  char ch[5];
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%s%lld%lld", ch, ql + i, qr + i);
    if (ch[0] == 'a')
      qt[i] = 1;
    else
      v.push_back(ql[i] - 1), v.push_back(qr[i]);
  }
  o = (long long)1 << n;
  v.push_back(-1), v.push_back(o - 1);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (i = 1; i < v.size(); i++) modify(rt, v[i - 1] + 1, v[i]);
  for (i = 0; i < n; i++) dfs(rt, rt, n - 1, i);
  for (i = 1; i <= m; i++) {
    if (!qt[i]) query(rt, ql[i], qr[i], i);
  }
  for (i = 1; i <= cnt; i++)
    if (!p[i]) ins(i);
  for (i = m; i >= 1; i--) {
    if (!qt[i]) {
      for (j = 0; j < g[i].size(); j++) ins(g[i][j]);
    } else {
      ql[i] = geta(rt, ql[i]);
      qr[i] = geta(rt, qr[i]);
      ans[i] = fnd(ql[i]) == fnd(qr[i]);
    }
  }
  for (i = 1; i <= m; i++)
    if (qt[i]) printf("%d\n", ans[i]);
  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 M = 55555;
const int W = M * 100;
int n, m, qt[M], ans[M];
long long o, ql[M], qr[M];
vector<long long> v;
int tot, cnt, ls[W], rs[W], a[W], rt, p[W];
vector<int> e[W], g[M];
void modify(int& k, long long L, long long R, long long l = 0,
            long long r = o - 1) {
  if (!k) k = ++tot;
  if (L <= l && r <= R) {
    a[k] = ++cnt;
    return;
  }
  long long h = l + r >> 1;
  if (L <= h) modify(ls[k], L, R, l, h);
  if (h < R) modify(rs[k], L, R, h + 1, r);
}
void dfs(int k1, int k2, int d, int D) {
  if (d > D) {
    if (a[k1]) return;
    dfs(ls[k1], ls[k2], d - 1, D);
    dfs(rs[k1], rs[k2], d - 1, D);
    return;
  }
  if (d == D) {
    if (a[k1]) return;
    dfs(ls[k1], rs[k2], d - 1, D);
    return;
  }
  if (a[k1] && a[k2]) {
    e[a[k1]].push_back(a[k2]);
    e[a[k2]].push_back(a[k1]);
    return;
  }
  if (a[k1]) {
    dfs(k1, ls[k2], d - 1, D);
    dfs(k1, rs[k2], d - 1, D);
    return;
  }
  if (a[k2]) {
    dfs(ls[k1], k2, d - 1, D);
    dfs(rs[k1], k2, d - 1, D);
    return;
  }
  dfs(ls[k1], ls[k2], d - 1, D);
  dfs(rs[k1], rs[k2], d - 1, D);
}
void query(int k, long long L, long long R, int i, long long l = 0,
           long long r = o - 1) {
  if (L <= l && r <= R) {
    p[a[k]] = i;
    g[i].push_back(a[k]);
    return;
  }
  long long h = l + r >> 1;
  if (L <= h) query(ls[k], L, R, i, l, h);
  if (h < R) query(rs[k], L, R, i, h + 1, r);
}
int f[W];
int fnd(int x) {
  if (f[x] == x) return x;
  return f[x] = fnd(f[x]);
}
void ins(int x) {
  int i;
  f[x] = x;
  for (i = 0; i < e[x].size(); i++)
    if (f[e[x][i]]) f[fnd(x)] = fnd(e[x][i]);
}
int geta(int k, long long x) {
  int i;
  for (i = n - 1; i >= 0; i--) {
    if ((x >> i) & 1)
      k = rs[k];
    else
      k = ls[k];
    if (a[k]) return a[k];
  }
}
int main() {
  int i, j;
  char ch[5];
  scanf("%d%d", &n, &m);
  for (i = 1; i <= m; i++) {
    scanf("%s%lld%lld", ch, ql + i, qr + i);
    if (ch[0] == 'a')
      qt[i] = 1;
    else
      v.push_back(ql[i] - 1), v.push_back(qr[i]);
  }
  o = (long long)1 << n;
  v.push_back(-1), v.push_back(o - 1);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (i = 1; i < v.size(); i++) modify(rt, v[i - 1] + 1, v[i]);
  for (i = 0; i < n; i++) dfs(rt, rt, n - 1, i);
  for (i = 1; i <= m; i++) {
    if (!qt[i]) query(rt, ql[i], qr[i], i);
  }
  for (i = 1; i <= cnt; i++)
    if (!p[i]) ins(i);
  for (i = m; i >= 1; i--) {
    if (!qt[i]) {
      for (j = 0; j < g[i].size(); j++) ins(g[i][j]);
    } else {
      ql[i] = geta(rt, ql[i]);
      qr[i] = geta(rt, qr[i]);
      ans[i] = fnd(ql[i]) == fnd(qr[i]);
    }
  }
  for (i = 1; i <= m; i++)
    if (qt[i]) printf("%d\n", ans[i]);
  return 0;
}

```