#include <bits/stdc++.h>
namespace {
using LL = long long;
struct Dsu {
  int n;
  std::vector<int> dsu;
  explicit Dsu(int n) : n(n), dsu(n) { std::iota(dsu.begin(), dsu.end(), 0); }
  int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
  bool is_connected(int x, int y) {
    x = find(x);
    y = find(y);
    return x == y;
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    dsu[x] = y;
    return true;
  }
};
struct Operation {
  std::string op;
  LL x, y;
};
struct Solver {
  int n, m;
  std::vector<Operation> ops;
  void solve(int ca, std::istream& reader) {
    reader >> n >> m;
    std::vector<LL> ss{0, (1LL << n)};
    for (int i = 0; i < m; ++i) {
      std::string op;
      LL x, y;
      reader >> op >> x >> y;
      ops.emplace_back(Operation{.op = op, .x = x, .y = y});
      if (op == "block") {
        ss.emplace_back(x);
        ss.emplace_back(y + 1);
      }
    }
    std::sort(ss.begin(), ss.end());
    ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
    ;
    for (int i = (int)ss.size() - 2; i >= 0; --i) {
      LL l = ss[i];
      LL r = ss[i + 1] - 1;
      int k = 0;
      while ((l >> k) != (r >> k)) {
        ++k;
      }
      if (k) {
        ss.emplace_back(r >> (k - 1) << (k - 1));
      }
    }
    std::sort(ss.begin(), ss.end());
    ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
    int tot = (int)ss.size() - 1;
    std::vector<std::vector<int>> graph(tot);
    Dsu dsu(tot);
    auto link = [&](int i, int j, int k) -> void {
      LL l = std::max(ss[i], ss[j] - (1LL << k));
      LL r = std::min(ss[i + 1], ss[j + 1] - (1LL << k)) - 1;
      assert(l <= r);
      if ((~l >> k & 1) || (~r >> k & 1) || (l >> k) != (r >> k)) {
        graph[i].emplace_back(j);
        graph[j].emplace_back(i);
      }
    };
    for (int k = 0; k < n; ++k) {
      LL d = 1LL << k;
      for (int i = 0, j = 0; i < tot; ++i) {
        while (j < tot && ss[j + 1] <= ss[i] + d) {
          ++j;
        }
        while (j < tot && ss[j + 1] <= ss[i + 1] + d) {
          link(i, j, k);
          ++j;
        }
        if (j < tot && ss[j] < ss[i + 1] + d) {
          link(i, j, k);
        }
      }
    };
    std::vector<char> mark(tot, true);
    for (int i = 0; i < m; ++i)
      if (ops[i].op == "block") {
        int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
        int r =
            std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
        for (int j = l; j < r; ++j) {
          mark[j] = false;
        }
      }
    for (int i = 0; i < tot; ++i)
      if (mark[i]) {
        for (int j : graph[i])
          if (mark[j]) {
            dsu.merge(i, j);
          }
      }
    std::vector<int> result(m, 0);
    for (int i = m - 1; i >= 0; --i) {
      if (ops[i].op == "block") {
        int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
        int r =
            std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
        for (int j = l; j < r; ++j) {
          mark[j] = true;
          for (int w : graph[j])
            if (mark[w]) {
              dsu.merge(j, w);
            }
        }
      } else {
        int x =
            std::upper_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin() - 1;
        int y =
            std::upper_bound(ss.begin(), ss.end(), ops[i].y) - ss.begin() - 1;
        result[i] = dsu.is_connected(x, y);
      }
    }
    for (int i = 0; i < m; ++i) {
      if (ops[i].op != "block") {
        printf("%d\n", result[i]);
      }
    }
  }
};
}  // namespace
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int cas = 1;
  for (int ca = 1; ca <= cas; ++ca) {
    Solver().solve(ca, reader);
  }
}

### 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>
namespace {
using LL = long long;
struct Dsu {
  int n;
  std::vector<int> dsu;
  explicit Dsu(int n) : n(n), dsu(n) { std::iota(dsu.begin(), dsu.end(), 0); }
  int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }
  bool is_connected(int x, int y) {
    x = find(x);
    y = find(y);
    return x == y;
  }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    dsu[x] = y;
    return true;
  }
};
struct Operation {
  std::string op;
  LL x, y;
};
struct Solver {
  int n, m;
  std::vector<Operation> ops;
  void solve(int ca, std::istream& reader) {
    reader >> n >> m;
    std::vector<LL> ss{0, (1LL << n)};
    for (int i = 0; i < m; ++i) {
      std::string op;
      LL x, y;
      reader >> op >> x >> y;
      ops.emplace_back(Operation{.op = op, .x = x, .y = y});
      if (op == "block") {
        ss.emplace_back(x);
        ss.emplace_back(y + 1);
      }
    }
    std::sort(ss.begin(), ss.end());
    ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
    ;
    for (int i = (int)ss.size() - 2; i >= 0; --i) {
      LL l = ss[i];
      LL r = ss[i + 1] - 1;
      int k = 0;
      while ((l >> k) != (r >> k)) {
        ++k;
      }
      if (k) {
        ss.emplace_back(r >> (k - 1) << (k - 1));
      }
    }
    std::sort(ss.begin(), ss.end());
    ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
    int tot = (int)ss.size() - 1;
    std::vector<std::vector<int>> graph(tot);
    Dsu dsu(tot);
    auto link = [&](int i, int j, int k) -> void {
      LL l = std::max(ss[i], ss[j] - (1LL << k));
      LL r = std::min(ss[i + 1], ss[j + 1] - (1LL << k)) - 1;
      assert(l <= r);
      if ((~l >> k & 1) || (~r >> k & 1) || (l >> k) != (r >> k)) {
        graph[i].emplace_back(j);
        graph[j].emplace_back(i);
      }
    };
    for (int k = 0; k < n; ++k) {
      LL d = 1LL << k;
      for (int i = 0, j = 0; i < tot; ++i) {
        while (j < tot && ss[j + 1] <= ss[i] + d) {
          ++j;
        }
        while (j < tot && ss[j + 1] <= ss[i + 1] + d) {
          link(i, j, k);
          ++j;
        }
        if (j < tot && ss[j] < ss[i + 1] + d) {
          link(i, j, k);
        }
      }
    };
    std::vector<char> mark(tot, true);
    for (int i = 0; i < m; ++i)
      if (ops[i].op == "block") {
        int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
        int r =
            std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
        for (int j = l; j < r; ++j) {
          mark[j] = false;
        }
      }
    for (int i = 0; i < tot; ++i)
      if (mark[i]) {
        for (int j : graph[i])
          if (mark[j]) {
            dsu.merge(i, j);
          }
      }
    std::vector<int> result(m, 0);
    for (int i = m - 1; i >= 0; --i) {
      if (ops[i].op == "block") {
        int l = std::lower_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin();
        int r =
            std::lower_bound(ss.begin(), ss.end(), ops[i].y + 1) - ss.begin();
        for (int j = l; j < r; ++j) {
          mark[j] = true;
          for (int w : graph[j])
            if (mark[w]) {
              dsu.merge(j, w);
            }
        }
      } else {
        int x =
            std::upper_bound(ss.begin(), ss.end(), ops[i].x) - ss.begin() - 1;
        int y =
            std::upper_bound(ss.begin(), ss.end(), ops[i].y) - ss.begin() - 1;
        result[i] = dsu.is_connected(x, y);
      }
    }
    for (int i = 0; i < m; ++i) {
      if (ops[i].op != "block") {
        printf("%d\n", result[i]);
      }
    }
  }
};
}  // namespace
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int cas = 1;
  for (int ca = 1; ca <= cas; ++ca) {
    Solver().solve(ca, reader);
  }
}

```