#include <bits/stdc++.h>
class disjoint_set {
 public:
 protected:
  std::vector<std::size_t> fa;

 public:
  disjoint_set(std::size_t n = 0) : fa(n) {
    std::iota(fa.begin(), fa.end(), 0);
  }
  std::size_t find(std::size_t x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
  }
  bool merge(std::size_t x, std::size_t y) {
    x = find(x), y = find(y);
    if (x == y) {
      return false;
    }
    fa[y] = x;
    return true;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  int n, m;
  std::cin >> n >> m;
  std::vector<std::tuple<int, long long, long long>> q;
  std::vector<long long> v;
  v.push_back(0);
  v.push_back(1ll << n);
  for (int i = 0; i < m; ++i) {
    std::string op;
    std::cin >> op;
    if (op == "block") {
      long long l, r;
      std::cin >> l >> r;
      ++r;
      v.push_back(l);
      v.push_back(r);
      q.emplace_back(0, l, r);
    } else {
      long long x, y;
      std::cin >> x >> y;
      q.emplace_back(1, x, y);
    }
  }
  std::reverse(q.begin(), q.end());
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  for (int i = 0, tmp = v.size(); i + 1 < tmp; ++i) {
    long long l = v[i], r = v[i + 1] - 1, x = 0;
    for (int j = n - 1; j >= 0; --j) {
      if ((l & 1ll << j) == (r & 1ll << j)) {
        x |= l & (1ll << j);
      } else {
        x |= 1ll << j;
        break;
      }
    }
    v.push_back(x);
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  int tot = (int)v.size() - 1;
  std::vector<std::vector<int>> E(tot);
  for (int i = 0; i < n; ++i) {
    for (int w = 0; w < 2; ++w) {
      for (int j = 0, p = 0; j < tot; ++j) {
        if ((v[j] >> i & 1) == w) {
          long long x = v[j] ^ (1ll << i);
          while (p < tot && x >= v[p + 1]) {
            ++p;
          }
          E[j].push_back(p);
          E[p].push_back(j);
        }
      }
    }
  }
  std::vector<bool> vis(tot, true);
  disjoint_set D(tot);
  auto add = [&](int u) {
    vis[u] = true;
    for (int v : E[u]) {
      if (vis[v]) {
        D.merge(u, v);
      }
    }
  };
  for (auto [op, l, r] : q) {
    if (op == 0) {
      int pl = std::lower_bound(v.begin(), v.end(), l) - v.begin();
      int pr = std::lower_bound(v.begin(), v.end(), r) - v.begin();
      for (int i = pl; i < pr; ++i) {
        vis[i] = false;
      }
    }
  }
  for (int i = 0; i < tot; ++i) {
    if (vis[i]) {
      add(i);
    }
  }
  std::vector<bool> ans;
  for (auto [op, l, r] : q) {
    if (op == 0) {
      int pl = std::lower_bound(v.begin(), v.end(), l) - v.begin();
      int pr = std::lower_bound(v.begin(), v.end(), r) - v.begin();
      for (int i = pl; i < pr; ++i) {
        add(i);
      }
    } else {
      int pl = std::upper_bound(v.begin(), v.end(), l) - v.begin() - 1;
      int pr = std::upper_bound(v.begin(), v.end(), r) - v.begin() - 1;
      ans.push_back(D.find(pl) == D.find(pr));
    }
  }
  std::reverse(ans.begin(), ans.end());
  for (auto v : ans) {
    std::cout << (int)v << "\n";
  }
}

### 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>
class disjoint_set {
 public:
 protected:
  std::vector<std::size_t> fa;

 public:
  disjoint_set(std::size_t n = 0) : fa(n) {
    std::iota(fa.begin(), fa.end(), 0);
  }
  std::size_t find(std::size_t x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
  }
  bool merge(std::size_t x, std::size_t y) {
    x = find(x), y = find(y);
    if (x == y) {
      return false;
    }
    fa[y] = x;
    return true;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  int n, m;
  std::cin >> n >> m;
  std::vector<std::tuple<int, long long, long long>> q;
  std::vector<long long> v;
  v.push_back(0);
  v.push_back(1ll << n);
  for (int i = 0; i < m; ++i) {
    std::string op;
    std::cin >> op;
    if (op == "block") {
      long long l, r;
      std::cin >> l >> r;
      ++r;
      v.push_back(l);
      v.push_back(r);
      q.emplace_back(0, l, r);
    } else {
      long long x, y;
      std::cin >> x >> y;
      q.emplace_back(1, x, y);
    }
  }
  std::reverse(q.begin(), q.end());
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  for (int i = 0, tmp = v.size(); i + 1 < tmp; ++i) {
    long long l = v[i], r = v[i + 1] - 1, x = 0;
    for (int j = n - 1; j >= 0; --j) {
      if ((l & 1ll << j) == (r & 1ll << j)) {
        x |= l & (1ll << j);
      } else {
        x |= 1ll << j;
        break;
      }
    }
    v.push_back(x);
  }
  std::sort(v.begin(), v.end());
  v.erase(std::unique(v.begin(), v.end()), v.end());
  int tot = (int)v.size() - 1;
  std::vector<std::vector<int>> E(tot);
  for (int i = 0; i < n; ++i) {
    for (int w = 0; w < 2; ++w) {
      for (int j = 0, p = 0; j < tot; ++j) {
        if ((v[j] >> i & 1) == w) {
          long long x = v[j] ^ (1ll << i);
          while (p < tot && x >= v[p + 1]) {
            ++p;
          }
          E[j].push_back(p);
          E[p].push_back(j);
        }
      }
    }
  }
  std::vector<bool> vis(tot, true);
  disjoint_set D(tot);
  auto add = [&](int u) {
    vis[u] = true;
    for (int v : E[u]) {
      if (vis[v]) {
        D.merge(u, v);
      }
    }
  };
  for (auto [op, l, r] : q) {
    if (op == 0) {
      int pl = std::lower_bound(v.begin(), v.end(), l) - v.begin();
      int pr = std::lower_bound(v.begin(), v.end(), r) - v.begin();
      for (int i = pl; i < pr; ++i) {
        vis[i] = false;
      }
    }
  }
  for (int i = 0; i < tot; ++i) {
    if (vis[i]) {
      add(i);
    }
  }
  std::vector<bool> ans;
  for (auto [op, l, r] : q) {
    if (op == 0) {
      int pl = std::lower_bound(v.begin(), v.end(), l) - v.begin();
      int pr = std::lower_bound(v.begin(), v.end(), r) - v.begin();
      for (int i = pl; i < pr; ++i) {
        add(i);
      }
    } else {
      int pl = std::upper_bound(v.begin(), v.end(), l) - v.begin() - 1;
      int pr = std::upper_bound(v.begin(), v.end(), r) - v.begin() - 1;
      ans.push_back(D.find(pl) == D.find(pr));
    }
  }
  std::reverse(ans.begin(), ans.end());
  for (auto v : ans) {
    std::cout << (int)v << "\n";
  }
}

```