#include <bits/stdc++.h>
using namespace std;
const int Inf = 0x3f3f3f3f;
const int maxnds = 3000005, maxm = 50005;
int N, M;
long long NN;
int op[maxm], ans[maxm];
long long lp[maxm], rp[maxm];
int son[maxnds][2], rt, nds;
int bel[maxnds];
map<long long, int> pos[55];
char tmp[20];
vector<pair<long long, long long> > ars;
vector<pair<int, int> > egs[maxm];
struct Segment {
  long long l, r;
  int id, p;
};
vector<Segment> ss;
struct UnionFind {
  int fa[maxnds];
  UnionFind() { memset(fa, -1, sizeof(fa)); }
  int inline root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); }
  bool inline conn(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return 0;
    if (fa[a] < fa[b]) swap(a, b);
    return fa[b] += fa[a], fa[a] = b, 1;
  }
} uf;
void inline build(long long l, long long r, int id, int &now, int dep = 0,
                  long long nl = 0, long long nr = NN - 1) {
  if (nl > r || nr < l) return;
  if (!now) now = ++nds;
  if (nl >= l && nr <= r) {
    bel[now] = id;
    pos[dep][nl] = now;
    return;
  }
  long long m = (nl + nr) >> 1;
  build(l, r, id, son[now][0], dep + 1, nl, m);
  build(l, r, id, son[now][1], dep + 1, m + 1, nr);
}
pair<int, int> inline solve(int now, long long nl = 0, long long nr = NN - 1) {
  if (bel[now]) {
    ss.push_back({nl, nr, bel[now], now});
    return make_pair(((int)(ss).size()) - 1, ((int)(ss).size()) - 1);
  }
  long long m = (nl + nr) >> 1, nmd = m - nl + 1;
  pair<int, int> ls = solve(son[now][0], nl, m);
  pair<int, int> rs = solve(son[now][1], m + 1, nr);
  for (int i = ls.first, j = rs.first; i <= ls.second && j <= rs.second;) {
    if (ss[i].l <= ss[j].r - nmd && ss[j].l - nmd <= ss[i].r) {
      egs[min(ss[i].id, ss[j].id)].emplace_back(ss[i].p, ss[j].p);
    }
    if (ss[i].r <= ss[j].r - nmd)
      ++i;
    else
      ++j;
  }
  return make_pair(ls.first, rs.second);
}
int main() {
  scanf("%d%d", &N, &M);
  NN = 1ll << N;
  for (int i = 1; i <= (M); ++i) {
    scanf("%s", tmp);
    scanf("%lld%lld", lp + i, rp + i);
    op[i] = 'b' - tmp[0];
    if (!op[i]) {
      ars.emplace_back(lp[i], rp[i]);
      build(lp[i], rp[i], i, rt);
    }
  }
  sort(ars.begin(), ars.end());
  long long lst = 0;
  for (int i = 0; i < (((int)(ars).size())); ++i) {
    if (lst < ars[i].first) build(lst, ars[i].first - 1, M + 1, rt);
    lst = ars[i].second + 1;
  }
  if (lst < NN) build(lst, NN - 1, M + 1, rt);
  solve(rt);
  for (int i = M + 1; i; --i) {
    for (auto &e : egs[i]) uf.conn(e.first, e.second);
    if (op[i]) {
      int lvl = N, lvr = N;
      long long ls = lp[i], rs = rp[i];
      while (!pos[lvl].count(ls)) {
        if ((ls >> (N - lvl)) & 1) ls ^= 1ll << (N - lvl);
        --lvl;
      }
      while (!pos[lvr].count(rs)) {
        if ((rs >> (N - lvr)) & 1) rs ^= 1ll << (N - lvr);
        --lvr;
      }
      ans[i] = uf.root(pos[lvl][ls]) == uf.root(pos[lvr][rs]);
    }
  }
  for (int i = 1; i <= (M); ++i)
    if (op[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 Inf = 0x3f3f3f3f;
const int maxnds = 3000005, maxm = 50005;
int N, M;
long long NN;
int op[maxm], ans[maxm];
long long lp[maxm], rp[maxm];
int son[maxnds][2], rt, nds;
int bel[maxnds];
map<long long, int> pos[55];
char tmp[20];
vector<pair<long long, long long> > ars;
vector<pair<int, int> > egs[maxm];
struct Segment {
  long long l, r;
  int id, p;
};
vector<Segment> ss;
struct UnionFind {
  int fa[maxnds];
  UnionFind() { memset(fa, -1, sizeof(fa)); }
  int inline root(int x) { return fa[x] < 0 ? x : fa[x] = root(fa[x]); }
  bool inline conn(int a, int b) {
    a = root(a);
    b = root(b);
    if (a == b) return 0;
    if (fa[a] < fa[b]) swap(a, b);
    return fa[b] += fa[a], fa[a] = b, 1;
  }
} uf;
void inline build(long long l, long long r, int id, int &now, int dep = 0,
                  long long nl = 0, long long nr = NN - 1) {
  if (nl > r || nr < l) return;
  if (!now) now = ++nds;
  if (nl >= l && nr <= r) {
    bel[now] = id;
    pos[dep][nl] = now;
    return;
  }
  long long m = (nl + nr) >> 1;
  build(l, r, id, son[now][0], dep + 1, nl, m);
  build(l, r, id, son[now][1], dep + 1, m + 1, nr);
}
pair<int, int> inline solve(int now, long long nl = 0, long long nr = NN - 1) {
  if (bel[now]) {
    ss.push_back({nl, nr, bel[now], now});
    return make_pair(((int)(ss).size()) - 1, ((int)(ss).size()) - 1);
  }
  long long m = (nl + nr) >> 1, nmd = m - nl + 1;
  pair<int, int> ls = solve(son[now][0], nl, m);
  pair<int, int> rs = solve(son[now][1], m + 1, nr);
  for (int i = ls.first, j = rs.first; i <= ls.second && j <= rs.second;) {
    if (ss[i].l <= ss[j].r - nmd && ss[j].l - nmd <= ss[i].r) {
      egs[min(ss[i].id, ss[j].id)].emplace_back(ss[i].p, ss[j].p);
    }
    if (ss[i].r <= ss[j].r - nmd)
      ++i;
    else
      ++j;
  }
  return make_pair(ls.first, rs.second);
}
int main() {
  scanf("%d%d", &N, &M);
  NN = 1ll << N;
  for (int i = 1; i <= (M); ++i) {
    scanf("%s", tmp);
    scanf("%lld%lld", lp + i, rp + i);
    op[i] = 'b' - tmp[0];
    if (!op[i]) {
      ars.emplace_back(lp[i], rp[i]);
      build(lp[i], rp[i], i, rt);
    }
  }
  sort(ars.begin(), ars.end());
  long long lst = 0;
  for (int i = 0; i < (((int)(ars).size())); ++i) {
    if (lst < ars[i].first) build(lst, ars[i].first - 1, M + 1, rt);
    lst = ars[i].second + 1;
  }
  if (lst < NN) build(lst, NN - 1, M + 1, rt);
  solve(rt);
  for (int i = M + 1; i; --i) {
    for (auto &e : egs[i]) uf.conn(e.first, e.second);
    if (op[i]) {
      int lvl = N, lvr = N;
      long long ls = lp[i], rs = rp[i];
      while (!pos[lvl].count(ls)) {
        if ((ls >> (N - lvl)) & 1) ls ^= 1ll << (N - lvl);
        --lvl;
      }
      while (!pos[lvr].count(rs)) {
        if ((rs >> (N - lvr)) & 1) rs ^= 1ll << (N - lvr);
        --lvr;
      }
      ans[i] = uf.root(pos[lvl][ls]) == uf.root(pos[lvr][rs]);
    }
  }
  for (int i = 1; i <= (M); ++i)
    if (op[i]) printf("%d\n", ans[i]);
  return 0;
}

```