#include <bits/stdc++.h>
using namespace std;
const int MAXQ = 5e4;
const int MAXN = 50;
int n, q;
int m, par[MAXQ * MAXN + 10], w[MAXQ * MAXN + 10], curBlockIdx;
bool isBlock[MAXQ * MAXN + 10];
vector<int> adj[MAXQ * MAXN + 10];
vector<pair<long long, long long> > blockRanges;
char s[10];
enum QueryType {
  ASK,
  BLOCK,
};
struct Query {
  QueryType queryType;
  long long u, v;
  vector<int> vertexIdx;
  int res;
};
Query queries[MAXQ];
struct Vertex {
  pair<long long, long long> range;
  int idx;
  Vertex() {}
  Vertex(const pair<long long, long long>& range, const int& idx)
      : range(range), idx(idx) {}
  bool operator<(const Vertex& other) const {
    return this->range < other.range;
  }
};
struct Node {
  list<Vertex> vertices;
  Node *lef, *rig;
  Node() : lef(NULL), rig(NULL) {}
};
Node* root = NULL;
void insert(const long long& u, const long long& v, Node*& node = root,
            const long long& lef = 0, const long long& rig = (1LL << n) - 1) {
  if (node == NULL) node = new Node;
  if (u == lef && v == rig) {
    node->vertices.push_back(Vertex(pair<long long, long long>(lef, rig), ++m));
    if (curBlockIdx != -1) {
      isBlock[m] = true;
      queries[curBlockIdx].vertexIdx.push_back(m);
    }
    return;
  }
  long long mid = (lef + rig) >> 1;
  if (v <= mid)
    insert(u, v, node->lef, lef, mid);
  else if (u > mid)
    insert(u, v, node->rig, mid + 1, rig);
  else {
    insert(u, mid, node->lef, lef, mid);
    insert(mid + 1, v, node->rig, mid + 1, rig);
  }
}
void merge(Node*& node, const long long& len) {
  list<Vertex>::iterator iterU = node->lef->vertices.begin(),
                         iterV = node->rig->vertices.begin(), iterUU, iterVV;
  do {
    iterUU = iterU, iterVV = iterV;
    adj[iterU->idx].push_back(iterV->idx);
    adj[iterV->idx].push_back(iterU->idx);
    if (iterU->range.second + len <= iterV->range.second) ++iterUU;
    if (iterV->range.second <= iterU->range.second + len) ++iterVV;
    iterU = iterUU, iterV = iterVV;
  } while (iterU != node->lef->vertices.end() ||
           iterV != node->rig->vertices.end());
  node->vertices.swap(node->lef->vertices);
  node->vertices.splice(node->vertices.end(), node->rig->vertices);
}
void init(Node*& node = root, const long long& lef = 0,
          const long long& rig = (1LL << n) - 1) {
  if (!node->vertices.empty()) return;
  long long mid = (lef + rig) >> 1;
  init(node->lef, lef, mid);
  init(node->rig, mid + 1, rig);
  merge(node, mid - lef + 1);
}
int findRoot(const int& u) {
  if (u == par[u]) return u;
  return par[u] = findRoot(par[u]);
}
void join(int u, int v) {
  if (isBlock[u] || isBlock[v]) return;
  u = findRoot(u), v = findRoot(v);
  if (u == v) return;
  if (w[u] < w[v]) swap(u, v);
  par[v] = u;
  w[u] += v;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int idx = 0; idx < q; ++idx) {
    scanf("%s %lld %lld", s, &queries[idx].u, &queries[idx].v);
    if (strcmp(s, "ask") == 0)
      queries[idx].queryType = QueryType::ASK;
    else {
      queries[idx].queryType = QueryType::BLOCK;
      curBlockIdx = idx;
      blockRanges.push_back(
          pair<long long, long long>(queries[idx].u, queries[idx].v));
      insert(queries[idx].u, queries[idx].v);
    }
  }
  curBlockIdx = -1;
  sort(blockRanges.begin(), blockRanges.end());
  if (blockRanges[0].first > 0) insert(0, blockRanges[0].first - 1);
  for (int idx = 0; idx < blockRanges.size(); ++idx) {
    if (idx + 1 < blockRanges.size()) {
      if (blockRanges[idx].second + 1 < blockRanges[idx + 1].first)
        insert(blockRanges[idx].second + 1, blockRanges[idx + 1].first - 1);
    } else {
      if (blockRanges[idx].second + 1 < (1LL << n))
        insert(blockRanges[idx].second + 1, (1LL << n) - 1);
    }
  }
  init();
  for (int i = 1; i <= m; ++i) {
    par[i] = i;
    w[i] = 1;
  }
  for (int u = 1; u <= m; ++u)
    for (const int& v : adj[u]) join(u, v);
  vector<Vertex> rootVertices(root->vertices.begin(), root->vertices.end());
  for (int idx = q - 1; idx >= 0; --idx)
    if (queries[idx].queryType == QueryType::ASK) {
      vector<Vertex>::iterator iter = upper_bound(
          rootVertices.begin(), rootVertices.end(),
          Vertex(pair<long long, long long>(queries[idx].u, 1LL << n), m + 1));
      --iter;
      int u = iter->idx;
      iter = upper_bound(
          rootVertices.begin(), rootVertices.end(),
          Vertex(pair<long long, long long>(queries[idx].v, 1LL << n), m + 1));
      --iter;
      int v = iter->idx;
      queries[idx].res = (findRoot(u) == findRoot(v) ? 1 : 0);
    } else {
      for (const int& u : queries[idx].vertexIdx) {
        isBlock[u] = false;
        for (const int& v : adj[u]) join(u, v);
      }
    }
  for (int idx = 0; idx < q; ++idx)
    if (queries[idx].queryType == QueryType::ASK)
      printf("%d\n", queries[idx].res);
  return 0;
}

### Prompt

Please create a solution in Cpp 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 int MAXQ = 5e4;
const int MAXN = 50;
int n, q;
int m, par[MAXQ * MAXN + 10], w[MAXQ * MAXN + 10], curBlockIdx;
bool isBlock[MAXQ * MAXN + 10];
vector<int> adj[MAXQ * MAXN + 10];
vector<pair<long long, long long> > blockRanges;
char s[10];
enum QueryType {
  ASK,
  BLOCK,
};
struct Query {
  QueryType queryType;
  long long u, v;
  vector<int> vertexIdx;
  int res;
};
Query queries[MAXQ];
struct Vertex {
  pair<long long, long long> range;
  int idx;
  Vertex() {}
  Vertex(const pair<long long, long long>& range, const int& idx)
      : range(range), idx(idx) {}
  bool operator<(const Vertex& other) const {
    return this->range < other.range;
  }
};
struct Node {
  list<Vertex> vertices;
  Node *lef, *rig;
  Node() : lef(NULL), rig(NULL) {}
};
Node* root = NULL;
void insert(const long long& u, const long long& v, Node*& node = root,
            const long long& lef = 0, const long long& rig = (1LL << n) - 1) {
  if (node == NULL) node = new Node;
  if (u == lef && v == rig) {
    node->vertices.push_back(Vertex(pair<long long, long long>(lef, rig), ++m));
    if (curBlockIdx != -1) {
      isBlock[m] = true;
      queries[curBlockIdx].vertexIdx.push_back(m);
    }
    return;
  }
  long long mid = (lef + rig) >> 1;
  if (v <= mid)
    insert(u, v, node->lef, lef, mid);
  else if (u > mid)
    insert(u, v, node->rig, mid + 1, rig);
  else {
    insert(u, mid, node->lef, lef, mid);
    insert(mid + 1, v, node->rig, mid + 1, rig);
  }
}
void merge(Node*& node, const long long& len) {
  list<Vertex>::iterator iterU = node->lef->vertices.begin(),
                         iterV = node->rig->vertices.begin(), iterUU, iterVV;
  do {
    iterUU = iterU, iterVV = iterV;
    adj[iterU->idx].push_back(iterV->idx);
    adj[iterV->idx].push_back(iterU->idx);
    if (iterU->range.second + len <= iterV->range.second) ++iterUU;
    if (iterV->range.second <= iterU->range.second + len) ++iterVV;
    iterU = iterUU, iterV = iterVV;
  } while (iterU != node->lef->vertices.end() ||
           iterV != node->rig->vertices.end());
  node->vertices.swap(node->lef->vertices);
  node->vertices.splice(node->vertices.end(), node->rig->vertices);
}
void init(Node*& node = root, const long long& lef = 0,
          const long long& rig = (1LL << n) - 1) {
  if (!node->vertices.empty()) return;
  long long mid = (lef + rig) >> 1;
  init(node->lef, lef, mid);
  init(node->rig, mid + 1, rig);
  merge(node, mid - lef + 1);
}
int findRoot(const int& u) {
  if (u == par[u]) return u;
  return par[u] = findRoot(par[u]);
}
void join(int u, int v) {
  if (isBlock[u] || isBlock[v]) return;
  u = findRoot(u), v = findRoot(v);
  if (u == v) return;
  if (w[u] < w[v]) swap(u, v);
  par[v] = u;
  w[u] += v;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int idx = 0; idx < q; ++idx) {
    scanf("%s %lld %lld", s, &queries[idx].u, &queries[idx].v);
    if (strcmp(s, "ask") == 0)
      queries[idx].queryType = QueryType::ASK;
    else {
      queries[idx].queryType = QueryType::BLOCK;
      curBlockIdx = idx;
      blockRanges.push_back(
          pair<long long, long long>(queries[idx].u, queries[idx].v));
      insert(queries[idx].u, queries[idx].v);
    }
  }
  curBlockIdx = -1;
  sort(blockRanges.begin(), blockRanges.end());
  if (blockRanges[0].first > 0) insert(0, blockRanges[0].first - 1);
  for (int idx = 0; idx < blockRanges.size(); ++idx) {
    if (idx + 1 < blockRanges.size()) {
      if (blockRanges[idx].second + 1 < blockRanges[idx + 1].first)
        insert(blockRanges[idx].second + 1, blockRanges[idx + 1].first - 1);
    } else {
      if (blockRanges[idx].second + 1 < (1LL << n))
        insert(blockRanges[idx].second + 1, (1LL << n) - 1);
    }
  }
  init();
  for (int i = 1; i <= m; ++i) {
    par[i] = i;
    w[i] = 1;
  }
  for (int u = 1; u <= m; ++u)
    for (const int& v : adj[u]) join(u, v);
  vector<Vertex> rootVertices(root->vertices.begin(), root->vertices.end());
  for (int idx = q - 1; idx >= 0; --idx)
    if (queries[idx].queryType == QueryType::ASK) {
      vector<Vertex>::iterator iter = upper_bound(
          rootVertices.begin(), rootVertices.end(),
          Vertex(pair<long long, long long>(queries[idx].u, 1LL << n), m + 1));
      --iter;
      int u = iter->idx;
      iter = upper_bound(
          rootVertices.begin(), rootVertices.end(),
          Vertex(pair<long long, long long>(queries[idx].v, 1LL << n), m + 1));
      --iter;
      int v = iter->idx;
      queries[idx].res = (findRoot(u) == findRoot(v) ? 1 : 0);
    } else {
      for (const int& u : queries[idx].vertexIdx) {
        isBlock[u] = false;
        for (const int& v : adj[u]) join(u, v);
      }
    }
  for (int idx = 0; idx < q; ++idx)
    if (queries[idx].queryType == QueryType::ASK)
      printf("%d\n", queries[idx].res);
  return 0;
}

```