#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
using namespace std;
const int N = 55, M = 200005;
struct DSU {
  int par[M], siz[M];
  inline void init(int n) {
    iota(par + 1, par + n + 1, 1);
    fill(siz + 1, siz + n + 1, 1);
  }
  int get(int x) {
    if (x == par[x]) return x;
    return par[x] = get(par[x]);
  }
  inline bool test(int x, int y) { return get(x) == get(y); }
  inline void merge(int x, int y) {
    if ((x = get(x)) == (y = get(y))) return;
    if (siz[x] < siz[y]) swap(x, y);
    par[y] = x, siz[x] += siz[y];
  }
} dsu;
int n, m, t[M], cnt, tot, tim[M];
long long a[M], b[M], p[M], ptr[M];
vector<int> g[M];
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    static char s[10];
    scanf("%s", s);
    if (s[0] == 'b') {
      read(a[i]), read(b[i]);
      p[++cnt] = a[i], p[++cnt] = ++b[i];
    } else {
      read(a[i]), read(b[i]);
      t[i] = 1;
    }
  }
  p[++cnt] = 0, p[++cnt] = 1ll << n;
  sort(p + 1, p + cnt + 1);
  cnt = unique(p + 1, p + cnt + 1) - p - 1;
  ptr[++tot] = 0;
  for (int i = 1; i < cnt; ++i) {
    long long l = p[i], r = p[i + 1] - 1;
    if (l == r) {
      ptr[++tot] = l;
    } else {
      for (int j = n - 1; ~j; --j) {
        if (!((l ^ r) >> j & 1)) continue;
        ptr[++tot] = l;
        r &= ((1ll << (n - j)) - 1) << j;
        ptr[++tot] = r;
        break;
      }
    }
  }
  ptr[++tot] = 1ll << n;
  tot = unique(ptr + 1, ptr + tot + 1) - ptr - 1;
  auto judge = [&](int i, int j, int k) {
    long long l1 = ptr[i], r1 = ptr[i + 1] - 1;
    long long l2 = ptr[j], r2 = ptr[j + 1] - 1;
    return (l2 - r1 <= (1ll << k)) && (r2 - l1 >= (1ll << k));
  };
  auto add_edge = [&](int i, int j, int k) {
    long long l1 = ptr[i], r1 = ptr[i + 1] - 1;
    long long l2 = ptr[j], r2 = ptr[j + 1] - 1;
    if (l1 >> k & 1)
      l1 += (!k) ? 1 : ((1ll << (k - 1)) - (l1 & ((1ll << k) - 1)));
    if (r1 >> k & 1) r1 -= (!k) ? 1 : ((r1 & ((1ll << k) - 1)) + 1);
    if (l1 > r1) return;
    if (!(l2 >> k & 1))
      l2 += (!k) ? 1 : ((1ll << (k - 1)) - (l2 & ((1ll << k) - 1)));
    if (!(r2 >> k & 1)) r2 -= (!k) ? 1 : ((r2 & ((1ll << k) - 1)) + 1);
    if (l2 > r2) return;
    if ((l2 - r1 <= (1ll << k)) && (r2 - l1 >= (1ll << k))) {
      if (tim[i] > tim[j]) swap(i, j);
      g[i].emplace_back(j);
    }
  };
  for (int i = 1; i < tot; ++i) tim[i] = m + 1;
  for (int i = 1; i <= m; ++i) {
    if (t[i]) continue;
    int pos = lower_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr;
    assert(ptr[pos] == a[i]);
    tim[pos] = i;
    if (a[i] + 1 != b[i]) tim[pos + 1] = i;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 1, j = 0; i < tot; ++i) {
      while (j && judge(j, i, k)) --j;
      for (; j + 1 < i && judge(j + 1, i, k); add_edge(++j, i, k))
        ;
    }
  }
  dsu.init(tot - 1);
  for (int i = 1; i < tot; ++i)
    if (tim[i] == m + 1)
      for (auto j : g[i]) dsu.merge(i, j);
  vector<int> ans;
  for (int i = m; i; --i) {
    if (t[i]) {
      int pa = upper_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr - 1;
      int pb = upper_bound(ptr + 1, ptr + tot + 1, b[i]) - ptr - 1;
      ans.emplace_back(dsu.test(pa, pb));
    } else {
      int u = lower_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr;
      for (auto v : g[u]) dsu.merge(u, v);
      if (a[i] + 1 != b[i]) {
        ++u;
        for (auto v : g[u]) dsu.merge(u, v);
      }
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto x : ans) printf("%d\n", x);
  return 0;
}

### Prompt

Your task is to create 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>
template <typename T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
using namespace std;
const int N = 55, M = 200005;
struct DSU {
  int par[M], siz[M];
  inline void init(int n) {
    iota(par + 1, par + n + 1, 1);
    fill(siz + 1, siz + n + 1, 1);
  }
  int get(int x) {
    if (x == par[x]) return x;
    return par[x] = get(par[x]);
  }
  inline bool test(int x, int y) { return get(x) == get(y); }
  inline void merge(int x, int y) {
    if ((x = get(x)) == (y = get(y))) return;
    if (siz[x] < siz[y]) swap(x, y);
    par[y] = x, siz[x] += siz[y];
  }
} dsu;
int n, m, t[M], cnt, tot, tim[M];
long long a[M], b[M], p[M], ptr[M];
vector<int> g[M];
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    static char s[10];
    scanf("%s", s);
    if (s[0] == 'b') {
      read(a[i]), read(b[i]);
      p[++cnt] = a[i], p[++cnt] = ++b[i];
    } else {
      read(a[i]), read(b[i]);
      t[i] = 1;
    }
  }
  p[++cnt] = 0, p[++cnt] = 1ll << n;
  sort(p + 1, p + cnt + 1);
  cnt = unique(p + 1, p + cnt + 1) - p - 1;
  ptr[++tot] = 0;
  for (int i = 1; i < cnt; ++i) {
    long long l = p[i], r = p[i + 1] - 1;
    if (l == r) {
      ptr[++tot] = l;
    } else {
      for (int j = n - 1; ~j; --j) {
        if (!((l ^ r) >> j & 1)) continue;
        ptr[++tot] = l;
        r &= ((1ll << (n - j)) - 1) << j;
        ptr[++tot] = r;
        break;
      }
    }
  }
  ptr[++tot] = 1ll << n;
  tot = unique(ptr + 1, ptr + tot + 1) - ptr - 1;
  auto judge = [&](int i, int j, int k) {
    long long l1 = ptr[i], r1 = ptr[i + 1] - 1;
    long long l2 = ptr[j], r2 = ptr[j + 1] - 1;
    return (l2 - r1 <= (1ll << k)) && (r2 - l1 >= (1ll << k));
  };
  auto add_edge = [&](int i, int j, int k) {
    long long l1 = ptr[i], r1 = ptr[i + 1] - 1;
    long long l2 = ptr[j], r2 = ptr[j + 1] - 1;
    if (l1 >> k & 1)
      l1 += (!k) ? 1 : ((1ll << (k - 1)) - (l1 & ((1ll << k) - 1)));
    if (r1 >> k & 1) r1 -= (!k) ? 1 : ((r1 & ((1ll << k) - 1)) + 1);
    if (l1 > r1) return;
    if (!(l2 >> k & 1))
      l2 += (!k) ? 1 : ((1ll << (k - 1)) - (l2 & ((1ll << k) - 1)));
    if (!(r2 >> k & 1)) r2 -= (!k) ? 1 : ((r2 & ((1ll << k) - 1)) + 1);
    if (l2 > r2) return;
    if ((l2 - r1 <= (1ll << k)) && (r2 - l1 >= (1ll << k))) {
      if (tim[i] > tim[j]) swap(i, j);
      g[i].emplace_back(j);
    }
  };
  for (int i = 1; i < tot; ++i) tim[i] = m + 1;
  for (int i = 1; i <= m; ++i) {
    if (t[i]) continue;
    int pos = lower_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr;
    assert(ptr[pos] == a[i]);
    tim[pos] = i;
    if (a[i] + 1 != b[i]) tim[pos + 1] = i;
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 1, j = 0; i < tot; ++i) {
      while (j && judge(j, i, k)) --j;
      for (; j + 1 < i && judge(j + 1, i, k); add_edge(++j, i, k))
        ;
    }
  }
  dsu.init(tot - 1);
  for (int i = 1; i < tot; ++i)
    if (tim[i] == m + 1)
      for (auto j : g[i]) dsu.merge(i, j);
  vector<int> ans;
  for (int i = m; i; --i) {
    if (t[i]) {
      int pa = upper_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr - 1;
      int pb = upper_bound(ptr + 1, ptr + tot + 1, b[i]) - ptr - 1;
      ans.emplace_back(dsu.test(pa, pb));
    } else {
      int u = lower_bound(ptr + 1, ptr + tot + 1, a[i]) - ptr;
      for (auto v : g[u]) dsu.merge(u, v);
      if (a[i] + 1 != b[i]) {
        ++u;
        for (auto v : g[u]) dsu.merge(u, v);
      }
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto x : ans) printf("%d\n", x);
  return 0;
}

```