#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long nax = 1e6 + 10, mod = 1e9 + 7, inf = 1e18;
struct node {
  vector<long long> par, sz;
  node(long long n) : par(n), sz(n) { iota(par.begin(), par.end(), 0); }
  long long find(long long v) {
    return v == par[v] ? v : par[v] = find(par[v]);
  }
  bool same(long long x, long long y) { return find(x) == find(y); }
  bool merge(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    sz[x] += sz[y];
    par[y] = x;
    return 1;
  }
  long long get(long long x) { return sz[find(x)]; }
};
void solve() {
  long long n, m;
  std::cin >> n >> m;
  std::vector<long long> v{0LL, 1LL << n};
  long long op[m];
  long long x[m], y[m];
  for (long long i = 0; i < m; i++) {
    std::string t;
    std::cin >> t;
    if (t == "block") {
      op[i] = 0;
      std::cin >> x[i] >> y[i];
      y[i]++;
      v.push_back(x[i]);
      v.push_back(y[i]);
    } else {
      op[i] = 1;
      std::cin >> x[i] >> y[i];
    }
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  long long N = v.size() - 1;
  for (long long i = 0; i < N; i++) {
    long long l = v[i];
    long long r = v[i + 1] - 1;
    long long k = 0;
    while ((l >> k) != (r >> k)) {
      k++;
    }
    if (k > 0) {
      v.push_back(r & ~((1LL << (k - 1)) - 1));
    }
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  N = v.size() - 1;
  node g(N);
  std::vector<long long> adj[N];
  auto add = [&](long long i, long long j, long long k) {
    long long l = std::max(v[i], v[j] - (1LL << k));
    long long r = std::min(v[i + 1], v[j + 1] - (1LL << k)) - 1;
    if ((~l >> k & 1) || (~r >> k & 1) || (l >> k) != (r >> k)) {
      adj[i].push_back(j);
      adj[j].push_back(i);
    }
  };
  for (long long k = 0; k < n; k++) {
    long long d = 1LL << k;
    for (long long i = 0, j = 0; i < N; i++) {
      while (j < N && v[j + 1] <= v[i] + d) {
        j++;
      }
      while (j < N && v[j + 1] <= v[i + 1] + d) {
        add(i, j, k);
        j++;
      }
      if (j < N && v[j] < v[i + 1] + d) {
        add(i, j, k);
      }
    }
  }
  bool vis[N];
  std::fill(vis, vis + N, true);
  for (long long i = 0; i < m; i++) {
    if (op[i] == 0) {
      long long j = std::lower_bound(v.begin(), v.end(), x[i]) - v.begin();
      while (v[j] < y[i]) {
        vis[j++] = false;
      }
    }
  }
  for (long long i = 0; i < N; i++) {
    if (vis[i]) {
      for (auto j : adj[i]) {
        if (vis[j]) {
          g.merge(i, j);
        }
      }
    }
  }
  long long res[m];
  for (long long i = m - 1; i >= 0; i--) {
    if (op[i] == 0) {
      long long j = std::lower_bound(v.begin(), v.end(), x[i]) - v.begin();
      while (v[j] < y[i]) {
        vis[j] = true;
        for (auto k : adj[j]) {
          if (vis[k]) {
            g.merge(j, k);
          }
        }
        j++;
      }
    } else {
      long long a = std::upper_bound(v.begin(), v.end(), x[i]) - v.begin() - 1;
      long long b = std::upper_bound(v.begin(), v.end(), y[i]) - v.begin() - 1;
      res[i] = g.same(a, b);
    }
  }
  for (long long i = 0; i < m; i++) {
    if (op[i] == 1) {
      std::cout << res[i] << "\n";
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long tt = 1;
  for (long long i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

<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 double PI = acos(-1);
const long long nax = 1e6 + 10, mod = 1e9 + 7, inf = 1e18;
struct node {
  vector<long long> par, sz;
  node(long long n) : par(n), sz(n) { iota(par.begin(), par.end(), 0); }
  long long find(long long v) {
    return v == par[v] ? v : par[v] = find(par[v]);
  }
  bool same(long long x, long long y) { return find(x) == find(y); }
  bool merge(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) return 0;
    sz[x] += sz[y];
    par[y] = x;
    return 1;
  }
  long long get(long long x) { return sz[find(x)]; }
};
void solve() {
  long long n, m;
  std::cin >> n >> m;
  std::vector<long long> v{0LL, 1LL << n};
  long long op[m];
  long long x[m], y[m];
  for (long long i = 0; i < m; i++) {
    std::string t;
    std::cin >> t;
    if (t == "block") {
      op[i] = 0;
      std::cin >> x[i] >> y[i];
      y[i]++;
      v.push_back(x[i]);
      v.push_back(y[i]);
    } else {
      op[i] = 1;
      std::cin >> x[i] >> y[i];
    }
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  long long N = v.size() - 1;
  for (long long i = 0; i < N; i++) {
    long long l = v[i];
    long long r = v[i + 1] - 1;
    long long k = 0;
    while ((l >> k) != (r >> k)) {
      k++;
    }
    if (k > 0) {
      v.push_back(r & ~((1LL << (k - 1)) - 1));
    }
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  N = v.size() - 1;
  node g(N);
  std::vector<long long> adj[N];
  auto add = [&](long long i, long long j, long long k) {
    long long l = std::max(v[i], v[j] - (1LL << k));
    long long r = std::min(v[i + 1], v[j + 1] - (1LL << k)) - 1;
    if ((~l >> k & 1) || (~r >> k & 1) || (l >> k) != (r >> k)) {
      adj[i].push_back(j);
      adj[j].push_back(i);
    }
  };
  for (long long k = 0; k < n; k++) {
    long long d = 1LL << k;
    for (long long i = 0, j = 0; i < N; i++) {
      while (j < N && v[j + 1] <= v[i] + d) {
        j++;
      }
      while (j < N && v[j + 1] <= v[i + 1] + d) {
        add(i, j, k);
        j++;
      }
      if (j < N && v[j] < v[i + 1] + d) {
        add(i, j, k);
      }
    }
  }
  bool vis[N];
  std::fill(vis, vis + N, true);
  for (long long i = 0; i < m; i++) {
    if (op[i] == 0) {
      long long j = std::lower_bound(v.begin(), v.end(), x[i]) - v.begin();
      while (v[j] < y[i]) {
        vis[j++] = false;
      }
    }
  }
  for (long long i = 0; i < N; i++) {
    if (vis[i]) {
      for (auto j : adj[i]) {
        if (vis[j]) {
          g.merge(i, j);
        }
      }
    }
  }
  long long res[m];
  for (long long i = m - 1; i >= 0; i--) {
    if (op[i] == 0) {
      long long j = std::lower_bound(v.begin(), v.end(), x[i]) - v.begin();
      while (v[j] < y[i]) {
        vis[j] = true;
        for (auto k : adj[j]) {
          if (vis[k]) {
            g.merge(j, k);
          }
        }
        j++;
      }
    } else {
      long long a = std::upper_bound(v.begin(), v.end(), x[i]) - v.begin() - 1;
      long long b = std::upper_bound(v.begin(), v.end(), y[i]) - v.begin() - 1;
      res[i] = g.same(a, b);
    }
  }
  for (long long i = 0; i < m; i++) {
    if (op[i] == 1) {
      std::cout << res[i] << "\n";
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long tt = 1;
  for (long long i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

```