#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<long long> p;
struct node1 {
  int t;
  long long x, y;
  void in() {
    static char opt[20];
    scanf("%s", opt);
    if (opt[0] == 'b') {
      t = 1;
    } else {
      t = 2;
    }
    scanf("%lld%lld", &x, &y);
    if (t == 1) {
      p.push_back(x);
      p.push_back(y + 1);
    }
  }
} q[50005];
struct ufs {
  const int n;
  vector<int> fa;
  ufs(int n) : n(n), fa(n) {
    for (int i = 0; i < n; ++i) fa[i] = i;
  }
  void reset() {
    for (int i = 0; i < n; ++i) fa[i] = i;
  }
  int fd(int k1) { return fa[k1] == k1 ? k1 : fa[k1] = fd(fa[k1]); }
  int mer(int k1, int k2) {
    k1 = fd(k1), k2 = fd(k2);
    if (k1 == k2) return 0;
    fa[k1] = k2;
    return 1;
  }
  bool chk(int k1, int k2) {
    k1 = fd(k1), k2 = fd(k2);
    return k1 == k2;
  }
};
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (m); ++i) q[i].in();
  p.push_back(0), p.push_back(1LL << n);
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  for (int i = (((int)(p).size()) - 2); i >= (0); --i) {
    if (p[i] + 1 == p[i + 1]) continue;
    int diff = 63 - __builtin_clzll(p[i] ^ (p[i + 1] - 1));
    long long mid = ((p[i] >> diff) + 1) << diff;
    if (p[i] <= mid && mid < p[i + 1]) {
      p.push_back(mid);
    }
  }
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  vector<vector<int> > e(((int)(p).size()) - 1, vector<int>());
  for (int bit = (0); bit <= (n - 1); ++bit) {
    int j = 0;
    for (int i = (0); i <= (((int)(p).size()) - 2); ++i) {
      long long pos = p[i] >> bit & 1 ? p[i] : ((p[i] >> bit) + 1) << bit;
      if (p[i] <= pos && pos < p[i + 1]) {
        while (j <= ((int)(p).size()) - 2 && pos - (1LL << bit) >= p[j + 1])
          ++j;
        if (j <= ((int)(p).size()) - 2 && i != j)
          e[i].push_back(j), e[j].push_back(i);
      }
    }
    j = 0;
    for (int i = (0); i <= (((int)(p).size()) - 2); ++i) {
      long long pos = ~(p[i]) >> bit & 1 ? p[i] : ((p[i] >> bit) + 1) << bit;
      if (p[i] <= pos && pos < p[i + 1]) {
        while (j <= ((int)(p).size()) - 2 && pos + (1LL << bit) >= p[j + 1])
          ++j;
        if (j <= ((int)(p).size()) - 2 && i != j)
          e[i].push_back(j), e[j].push_back(i);
      }
    }
  }
  vector<int> ban(((int)(p).size()) - 1);
  for (int i = (1); i <= (m); ++i) {
    int t = q[i].t;
    long long x = q[i].x, y = q[i].y;
    if (t == 1) {
      ban[upper_bound(p.begin(), p.end(), x) - p.begin() - 1] = 1;
      ban[upper_bound(p.begin(), p.end(), y) - p.begin() - 1] = 1;
    }
  }
  ufs o(((int)(p).size()) - 1);
  for (int i = (0); i <= (((int)(p).size()) - 2); ++i)
    if (!ban[i])
      for (auto x : e[i])
        if (!ban[x]) o.mer(i, x);
  vector<int> ans;
  for (int i = (m); i >= (1); --i) {
    int t = q[i].t;
    long long x = q[i].x, y = q[i].y;
    int k1 = upper_bound(p.begin(), p.end(), x) - p.begin() - 1;
    int k2 = upper_bound(p.begin(), p.end(), y) - p.begin() - 1;
    if (t == 1) {
      ban[k1] = ban[k2] = 0;
      for (auto x : e[k1])
        if (!ban[x]) o.mer(k1, x);
      for (auto x : e[k2])
        if (!ban[x]) o.mer(k2, x);
    } else {
      ans.push_back(o.chk(k1, k2));
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto x : ans) printf("%d\n", x);
  return 0;
}

### 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;
int n, m;
vector<long long> p;
struct node1 {
  int t;
  long long x, y;
  void in() {
    static char opt[20];
    scanf("%s", opt);
    if (opt[0] == 'b') {
      t = 1;
    } else {
      t = 2;
    }
    scanf("%lld%lld", &x, &y);
    if (t == 1) {
      p.push_back(x);
      p.push_back(y + 1);
    }
  }
} q[50005];
struct ufs {
  const int n;
  vector<int> fa;
  ufs(int n) : n(n), fa(n) {
    for (int i = 0; i < n; ++i) fa[i] = i;
  }
  void reset() {
    for (int i = 0; i < n; ++i) fa[i] = i;
  }
  int fd(int k1) { return fa[k1] == k1 ? k1 : fa[k1] = fd(fa[k1]); }
  int mer(int k1, int k2) {
    k1 = fd(k1), k2 = fd(k2);
    if (k1 == k2) return 0;
    fa[k1] = k2;
    return 1;
  }
  bool chk(int k1, int k2) {
    k1 = fd(k1), k2 = fd(k2);
    return k1 == k2;
  }
};
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (m); ++i) q[i].in();
  p.push_back(0), p.push_back(1LL << n);
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  for (int i = (((int)(p).size()) - 2); i >= (0); --i) {
    if (p[i] + 1 == p[i + 1]) continue;
    int diff = 63 - __builtin_clzll(p[i] ^ (p[i + 1] - 1));
    long long mid = ((p[i] >> diff) + 1) << diff;
    if (p[i] <= mid && mid < p[i + 1]) {
      p.push_back(mid);
    }
  }
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  vector<vector<int> > e(((int)(p).size()) - 1, vector<int>());
  for (int bit = (0); bit <= (n - 1); ++bit) {
    int j = 0;
    for (int i = (0); i <= (((int)(p).size()) - 2); ++i) {
      long long pos = p[i] >> bit & 1 ? p[i] : ((p[i] >> bit) + 1) << bit;
      if (p[i] <= pos && pos < p[i + 1]) {
        while (j <= ((int)(p).size()) - 2 && pos - (1LL << bit) >= p[j + 1])
          ++j;
        if (j <= ((int)(p).size()) - 2 && i != j)
          e[i].push_back(j), e[j].push_back(i);
      }
    }
    j = 0;
    for (int i = (0); i <= (((int)(p).size()) - 2); ++i) {
      long long pos = ~(p[i]) >> bit & 1 ? p[i] : ((p[i] >> bit) + 1) << bit;
      if (p[i] <= pos && pos < p[i + 1]) {
        while (j <= ((int)(p).size()) - 2 && pos + (1LL << bit) >= p[j + 1])
          ++j;
        if (j <= ((int)(p).size()) - 2 && i != j)
          e[i].push_back(j), e[j].push_back(i);
      }
    }
  }
  vector<int> ban(((int)(p).size()) - 1);
  for (int i = (1); i <= (m); ++i) {
    int t = q[i].t;
    long long x = q[i].x, y = q[i].y;
    if (t == 1) {
      ban[upper_bound(p.begin(), p.end(), x) - p.begin() - 1] = 1;
      ban[upper_bound(p.begin(), p.end(), y) - p.begin() - 1] = 1;
    }
  }
  ufs o(((int)(p).size()) - 1);
  for (int i = (0); i <= (((int)(p).size()) - 2); ++i)
    if (!ban[i])
      for (auto x : e[i])
        if (!ban[x]) o.mer(i, x);
  vector<int> ans;
  for (int i = (m); i >= (1); --i) {
    int t = q[i].t;
    long long x = q[i].x, y = q[i].y;
    int k1 = upper_bound(p.begin(), p.end(), x) - p.begin() - 1;
    int k2 = upper_bound(p.begin(), p.end(), y) - p.begin() - 1;
    if (t == 1) {
      ban[k1] = ban[k2] = 0;
      for (auto x : e[k1])
        if (!ban[x]) o.mer(k1, x);
      for (auto x : e[k2])
        if (!ban[x]) o.mer(k2, x);
    } else {
      ans.push_back(o.chk(k1, k2));
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto x : ans) printf("%d\n", x);
  return 0;
}

```