#include <bits/stdc++.h>
const int M = 5e4 + 5;
const int N = M << 6;
int n, m;
int ans[M];
long long U;
struct query {
  std::string opt;
  long long x, y;
} qry[M];
std::vector<std::pair<int, int>> edge[M];
int tot = 1, lc[N], rc[N];
int rec[N], uset[N];
int find(int x) { return x == uset[x] ? x : uset[x] = find(uset[x]); }
void pushdown(int x) {
  if (!lc[x]) lc[x] = ++tot;
  if (!rc[x]) rc[x] = ++tot;
  if (rec[x]) rec[lc[x]] = rec[rc[x]] = rec[x], rec[x] = 0;
}
void insert(int x, long long l, long long r, long long ql, long long qr,
            int t) {
  if (ql > r || l > qr) return;
  if (ql <= l && r <= qr) {
    rec[x] = t;
    return;
  }
  pushdown(x);
  insert(lc[x], l, ((l + r) >> 1), ql, qr, t);
  insert(rc[x], ((l + r) >> 1) + 1, r, ql, qr, t);
}
void connect(int x, int y) {
  if ((!lc[x] && !rc[x]) && (!lc[y] && !rc[y]))
    return (void)edge[std::min(rec[x], rec[y])].emplace_back(x, y);
  if ((!lc[x] && !rc[x])) return connect(x, lc[y]), connect(x, rc[y]);
  if ((!lc[y] && !rc[y])) return connect(lc[x], y), connect(rc[x], y);
  connect(lc[x], lc[y]), connect(rc[x], rc[y]);
}
int locate(int x, long long l, long long r, long long p) {
  if ((!lc[x] && !rc[x])) return x;
  if (p <= ((l + r) >> 1))
    return locate(lc[x], l, ((l + r) >> 1), p);
  else
    return locate(rc[x], ((l + r) >> 1) + 1, r, p);
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n >> m;
  U = (1ll << n) - 1;
  rec[1] = m + 1;
  for (int i = 1; i <= m; i++) {
    std::cin >> qry[i].opt >> qry[i].x >> qry[i].y;
    if (qry[i].opt == "block") insert(1, 0, U, qry[i].x, qry[i].y, i);
  }
  for (int i = 1; i <= tot; i++)
    if (!(!lc[i] && !rc[i])) connect(lc[i], rc[i]);
  for (int i = 1; i <= tot; i++) uset[i] = i;
  for (auto [x, y] : edge[m + 1]) uset[find(x)] = find(y);
  for (int i = m; i; --i) {
    for (auto [x, y] : edge[i]) uset[find(x)] = find(y);
    if (qry[i].opt == "ask")
      ans[i] =
          find(locate(1, 0, U, qry[i].x)) == find(locate(1, 0, U, qry[i].y));
  }
  for (int i = 1; i <= m; i++)
    if (qry[i].opt == "ask") std::cout << ans[i] << "\n";
  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>
const int M = 5e4 + 5;
const int N = M << 6;
int n, m;
int ans[M];
long long U;
struct query {
  std::string opt;
  long long x, y;
} qry[M];
std::vector<std::pair<int, int>> edge[M];
int tot = 1, lc[N], rc[N];
int rec[N], uset[N];
int find(int x) { return x == uset[x] ? x : uset[x] = find(uset[x]); }
void pushdown(int x) {
  if (!lc[x]) lc[x] = ++tot;
  if (!rc[x]) rc[x] = ++tot;
  if (rec[x]) rec[lc[x]] = rec[rc[x]] = rec[x], rec[x] = 0;
}
void insert(int x, long long l, long long r, long long ql, long long qr,
            int t) {
  if (ql > r || l > qr) return;
  if (ql <= l && r <= qr) {
    rec[x] = t;
    return;
  }
  pushdown(x);
  insert(lc[x], l, ((l + r) >> 1), ql, qr, t);
  insert(rc[x], ((l + r) >> 1) + 1, r, ql, qr, t);
}
void connect(int x, int y) {
  if ((!lc[x] && !rc[x]) && (!lc[y] && !rc[y]))
    return (void)edge[std::min(rec[x], rec[y])].emplace_back(x, y);
  if ((!lc[x] && !rc[x])) return connect(x, lc[y]), connect(x, rc[y]);
  if ((!lc[y] && !rc[y])) return connect(lc[x], y), connect(rc[x], y);
  connect(lc[x], lc[y]), connect(rc[x], rc[y]);
}
int locate(int x, long long l, long long r, long long p) {
  if ((!lc[x] && !rc[x])) return x;
  if (p <= ((l + r) >> 1))
    return locate(lc[x], l, ((l + r) >> 1), p);
  else
    return locate(rc[x], ((l + r) >> 1) + 1, r, p);
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  std::cin >> n >> m;
  U = (1ll << n) - 1;
  rec[1] = m + 1;
  for (int i = 1; i <= m; i++) {
    std::cin >> qry[i].opt >> qry[i].x >> qry[i].y;
    if (qry[i].opt == "block") insert(1, 0, U, qry[i].x, qry[i].y, i);
  }
  for (int i = 1; i <= tot; i++)
    if (!(!lc[i] && !rc[i])) connect(lc[i], rc[i]);
  for (int i = 1; i <= tot; i++) uset[i] = i;
  for (auto [x, y] : edge[m + 1]) uset[find(x)] = find(y);
  for (int i = m; i; --i) {
    for (auto [x, y] : edge[i]) uset[find(x)] = find(y);
    if (qry[i].opt == "ask")
      ans[i] =
          find(locate(1, 0, U, qry[i].x)) == find(locate(1, 0, U, qry[i].y));
  }
  for (int i = 1; i <= m; i++)
    if (qry[i].opt == "ask") std::cout << ans[i] << "\n";
  return 0;
}

```