#include <bits/stdc++.h>
using namespace std;
const int N = (int)5e4 + 5;
vector<pair<long long, long long> > segs, sg;
vector<pair<int, int> > ins[N];
int pr[40 * N];
long long l[N], r[N];
int n, q;
int tp[N], ans[N];
void div(int bit, long long l, long long r) {
  long long siz = (1ll << (bit + 1)) - 1;
  long long l_s = l & siz;
  long long r_s = r & siz;
  if (!l_s && r_s == siz) {
    segs.push_back({l, r});
    return;
  }
  if (l_s >= (1ll << bit)) {
    div(bit - 1, l, r);
  } else {
    if (r_s < (1ll << bit)) {
      div(bit - 1, l, r);
    } else {
      long long md = l | ((1ll << bit) - 1);
      div(bit - 1, l, md);
      div(bit - 1, md + 1, r);
    }
  }
}
int f(int v) { return (pr[v] == v ? v : pr[v] = f(pr[v])); }
void link(int v, int u) {
  v = f(v);
  u = f(u);
  if (v == u) {
    return;
  }
  pr[u] = v;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> n >> q;
  for (int i = 0; i < q; i++) {
    cin >> s >> l[i] >> r[i];
    if (s == "ask") {
      tp[i] = 0;
    } else {
      tp[i] = 1;
      sg.push_back({l[i], r[i]});
    }
  }
  vector<pair<long long, long long> > nsg;
  sort((sg).begin(), (sg).end());
  if ((int)sg.size() == 0) {
    sg.push_back({0, (1ll << n) - 1});
  }
  if (sg[0].first != 0) {
    nsg.push_back({0, sg[0].first - 1});
  }
  for (int i = 0; i < (int)sg.size(); i++) {
    nsg.push_back(sg[i]);
    if (i + 1 < (int)sg.size() && sg[i].second + 1 <= sg[i + 1].first - 1) {
      nsg.push_back({sg[i].second + 1, sg[i + 1].first - 1});
    }
  }
  if (sg.back().second + 1 <= (1ll << n) - 1) {
    nsg.push_back({sg.back().second + 1, (1ll << n) - 1});
  }
  for (auto &x : nsg) {
    div(n - 1, x.first, x.second);
  }
  vector<int> tm((int)segs.size());
  for (int i = 0; i < (int)segs.size(); i++) {
    tm[i] = -1;
  }
  for (int i = 0; i < q; i++) {
    if (!tp[i]) {
      continue;
    }
    int L = lower_bound((segs).begin(), (segs).end(), make_pair(l[i], -1ll)) -
            segs.begin();
    int R =
        lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
        segs.begin();
    for (int j = L; j < R; j++) {
      tm[j] = i;
    }
  }
  for (int i = 0; i < (int)segs.size(); i++) {
    if (tm[i] == -1) {
      tm[i] = q;
    }
  }
  vector<int> sb[2];
  for (int i = 0; i < n; i++) {
    sb[0].clear();
    sb[1].clear();
    for (int j = 0; j < (int)segs.size(); j++) {
      long long L = segs[j].first;
      long long R = segs[j].second;
      if ((1ll << i) >= R - L + 1) {
        assert(((R >> i) & 1) == ((L >> i) & 1));
        sb[((R >> i) & 1)].push_back(j);
      }
    }
    for (int b = 0; b < 2; b++) {
      int p = 0;
      for (int j = 0; j < (int)sb[b].size(); j++) {
        int id = sb[b][j];
        long long L = segs[id].first ^ (1ll << i);
        while (segs[p].second < L) {
          p++;
        }
        if (segs[p].second - segs[p].first >=
            segs[id].second - segs[id].first) {
          int tim = min(tm[p], tm[id]);
          ins[tim].push_back({p, id});
        }
      }
    }
  }
  for (int i = 0; i < (int)segs.size(); i++) {
    pr[i] = i;
  }
  for (int i = q; i >= 0; i--) {
    for (auto &x : ins[i]) {
      link(x.first, x.second);
    }
    if (i < q && !tp[i]) {
      int v =
          lower_bound((segs).begin(), (segs).end(), make_pair(l[i] + 1, -1ll)) -
          segs.begin() - 1;
      int u =
          lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
          segs.begin() - 1;
      ans[i] = (f(v) == f(u));
    }
  }
  for (int i = 0; i < q; i++) {
    if (!tp[i]) {
      cout << ans[i] << '\n';
    }
  }
}

### Prompt

Please provide a Cpp coded solution 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 N = (int)5e4 + 5;
vector<pair<long long, long long> > segs, sg;
vector<pair<int, int> > ins[N];
int pr[40 * N];
long long l[N], r[N];
int n, q;
int tp[N], ans[N];
void div(int bit, long long l, long long r) {
  long long siz = (1ll << (bit + 1)) - 1;
  long long l_s = l & siz;
  long long r_s = r & siz;
  if (!l_s && r_s == siz) {
    segs.push_back({l, r});
    return;
  }
  if (l_s >= (1ll << bit)) {
    div(bit - 1, l, r);
  } else {
    if (r_s < (1ll << bit)) {
      div(bit - 1, l, r);
    } else {
      long long md = l | ((1ll << bit) - 1);
      div(bit - 1, l, md);
      div(bit - 1, md + 1, r);
    }
  }
}
int f(int v) { return (pr[v] == v ? v : pr[v] = f(pr[v])); }
void link(int v, int u) {
  v = f(v);
  u = f(u);
  if (v == u) {
    return;
  }
  pr[u] = v;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string s;
  cin >> n >> q;
  for (int i = 0; i < q; i++) {
    cin >> s >> l[i] >> r[i];
    if (s == "ask") {
      tp[i] = 0;
    } else {
      tp[i] = 1;
      sg.push_back({l[i], r[i]});
    }
  }
  vector<pair<long long, long long> > nsg;
  sort((sg).begin(), (sg).end());
  if ((int)sg.size() == 0) {
    sg.push_back({0, (1ll << n) - 1});
  }
  if (sg[0].first != 0) {
    nsg.push_back({0, sg[0].first - 1});
  }
  for (int i = 0; i < (int)sg.size(); i++) {
    nsg.push_back(sg[i]);
    if (i + 1 < (int)sg.size() && sg[i].second + 1 <= sg[i + 1].first - 1) {
      nsg.push_back({sg[i].second + 1, sg[i + 1].first - 1});
    }
  }
  if (sg.back().second + 1 <= (1ll << n) - 1) {
    nsg.push_back({sg.back().second + 1, (1ll << n) - 1});
  }
  for (auto &x : nsg) {
    div(n - 1, x.first, x.second);
  }
  vector<int> tm((int)segs.size());
  for (int i = 0; i < (int)segs.size(); i++) {
    tm[i] = -1;
  }
  for (int i = 0; i < q; i++) {
    if (!tp[i]) {
      continue;
    }
    int L = lower_bound((segs).begin(), (segs).end(), make_pair(l[i], -1ll)) -
            segs.begin();
    int R =
        lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
        segs.begin();
    for (int j = L; j < R; j++) {
      tm[j] = i;
    }
  }
  for (int i = 0; i < (int)segs.size(); i++) {
    if (tm[i] == -1) {
      tm[i] = q;
    }
  }
  vector<int> sb[2];
  for (int i = 0; i < n; i++) {
    sb[0].clear();
    sb[1].clear();
    for (int j = 0; j < (int)segs.size(); j++) {
      long long L = segs[j].first;
      long long R = segs[j].second;
      if ((1ll << i) >= R - L + 1) {
        assert(((R >> i) & 1) == ((L >> i) & 1));
        sb[((R >> i) & 1)].push_back(j);
      }
    }
    for (int b = 0; b < 2; b++) {
      int p = 0;
      for (int j = 0; j < (int)sb[b].size(); j++) {
        int id = sb[b][j];
        long long L = segs[id].first ^ (1ll << i);
        while (segs[p].second < L) {
          p++;
        }
        if (segs[p].second - segs[p].first >=
            segs[id].second - segs[id].first) {
          int tim = min(tm[p], tm[id]);
          ins[tim].push_back({p, id});
        }
      }
    }
  }
  for (int i = 0; i < (int)segs.size(); i++) {
    pr[i] = i;
  }
  for (int i = q; i >= 0; i--) {
    for (auto &x : ins[i]) {
      link(x.first, x.second);
    }
    if (i < q && !tp[i]) {
      int v =
          lower_bound((segs).begin(), (segs).end(), make_pair(l[i] + 1, -1ll)) -
          segs.begin() - 1;
      int u =
          lower_bound((segs).begin(), (segs).end(), make_pair(r[i] + 1, -1ll)) -
          segs.begin() - 1;
      ans[i] = (f(v) == f(u));
    }
  }
  for (int i = 0; i < q; i++) {
    if (!tp[i]) {
      cout << ans[i] << '\n';
    }
  }
}

```