#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = numeric_limits<double>::infinity();
const double DNAN = numeric_limits<double>::quiet_NaN();
const double EPS = 1e-9;
const double PI = acos((double)-1.0);
const int DX[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int DY[] = {0, 1, 0, -1, 1, -1, -1, 1};
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long sqr(long long x) { return x * x; }
long long sqr(int x) { return (long long)x * x; }
double sqr(double x) { return x * x; }
mt19937 mmtw(960172);
long long rnd(long long x, long long y) {
  static uniform_int_distribution<long long> d;
  return d(mmtw) % (y - x + 1) + x;
}
template <typename T>
T& updMin(T& a, T const& b) {
  if (b < a) a = b;
  return a;
}
template <typename T>
T& updMax(T& a, T const& b) {
  if (a < b) a = b;
  return a;
}
long long divFloor(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? a / b : (a - b + 1) / b;
}
long long divCeil(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? (a + b - 1) / b : a / b;
}
long long divFloorS(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? (a + b - 1) / b - 1 : a / b - 1;
}
long long divCeilS(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? a / b + 1 : (a - b + 1) / b + 1;
}
template <typename K, typename V>
V getOrDef(map<K, V> const& a, K const& k, V const& def = V()) {
  auto it = a.find(k);
  return it == a.end() ? def : it->second;
}
template <typename K, typename V>
V getOrDef(unordered_map<K, V> const& a, K const& k, V const& def = V()) {
  auto it = a.find(k);
  return it == a.end() ? def : it->second;
}
template <typename A, typename B>
istream& operator>>(istream& in, pair<A, B>& p) {
  return in >> p.first >> p.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> const& p) {
  return out << p.first << " " << p.second;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& a) {
  for (T& x : a) in >> x;
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& a) {
  bool f = true;
  for (T const& x : a) {
    if (!f) out << " ";
    f = false;
    out << x;
  }
  return out;
}
template <typename T>
bool isZero(T const& x) {
  return x == T(0);
}
bool isZero(float x) { return abs(x) < EPS; }
bool isZero(double x) { return abs(x) < EPS; }
bool isZero(long double x) { return abs(x) < EPS; }
template <typename T>
int sgn(T const& x) {
  if (isZero(x)) return 0;
  return x > 0 ? 1 : -1;
}
struct Node {
  long long cl, cr;
  Node* l = nullptr;
  Node* r = nullptr;
  int id = -1;
  bool leaf = true;
  bool destroyed = 0;
  Node(long long cl, long long cr) : cl(cl), cr(cr) {}
};
struct Query {
  bool destroy;
  long long a, b;
};
void down1(long long l, long long r, Node* c) {
  if (l >= c->cr || c->cl >= r) return;
  if (l <= c->cl && c->cr <= r) {
    assert(c->leaf);
    c->destroyed = 1;
    return;
  }
  if (c->leaf) {
    assert(!c->destroyed);
    c->leaf = 0;
    long long mid = (c->cl + c->cr) / 2;
    c->l = new Node(c->cl, mid);
    c->r = new Node(mid, c->cr);
  }
  down1(l, r, c->l);
  down1(l, r, c->r);
}
vector<Node*> leafs;
vector<long long> cls;
void dfs2(Node* c) {
  if (c->leaf) {
    leafs.push_back(c);
    cls.push_back(c->cl);
  } else {
    dfs2(c->l);
    dfs2(c->r);
  }
}
struct DSU {
  vector<int> p;
  DSU() = default;
  DSU(int n) : p(n, -1) {}
  int get(int v) { return p[v] == -1 ? v : p[v] = get(p[v]); }
  bool merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return false;
    p[y] = x;
    return true;
  }
} dsu;
int k;
Node* root;
int main() {
  ios::sync_with_stdio(false);
  int qn;
  cin >> k >> qn;
  long long n = 1LL << k;
  vector<Query> qs;
  root = new Node(0, n);
  for (int i = 0; i < qn; ++i) {
    string type;
    long long a, b;
    cin >> type >> a >> b;
    if (type == "block") {
      qs.push_back({1, a, b + 1});
      down1(a, b + 1, root);
    } else {
      qs.push_back({0, a, b});
    }
  }
  dfs2(root);
  for (int i = 0; i < ((int)((leafs).size())); ++i) leafs[i]->id = i;
  dsu = DSU(((int)((leafs).size())));
  for (int id = 0; id < ((int)((leafs).size())); ++id) {
    Node* c = leafs[id];
    if (c->destroyed) continue;
    long long len = c->cr - c->cl;
    for (int i = 0; i < k; ++i) {
      if ((1LL << i) < len) continue;
      long long nl = c->cl ^ (1LL << i);
      long long nr = nl + len;
      int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
      while (j < ((int)((cls).size())) && cls[j] < nr) {
        if (!leafs[j]->destroyed) dsu.merge(id, j);
        j++;
      }
    }
  }
  vector<int> ans;
  reverse((qs).begin(), (qs).end());
  for (Query const& q : qs) {
    if (q.destroy) {
      int id1 = lower_bound((cls).begin(), (cls).end(), q.a) - cls.begin();
      int id2 = lower_bound((cls).begin(), (cls).end(), q.b) - cls.begin();
      for (int id = id1; id < id2; ++id) {
        Node* c = leafs[id];
        c->destroyed = false;
        long long len = c->cr - c->cl;
        for (int i = 0; i < k; ++i) {
          if ((1LL << i) < len) continue;
          long long nl = c->cl ^ (1LL << i);
          long long nr = nl + len;
          int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
          while (j < ((int)((cls).size())) && cls[j] < nr) {
            if (!leafs[j]->destroyed) dsu.merge(id, j);
            j++;
          }
        }
      }
    } else {
      int id1 = upper_bound((cls).begin(), (cls).end(), q.a) - cls.begin() - 1;
      int id2 = upper_bound((cls).begin(), (cls).end(), q.b) - cls.begin() - 1;
      ans.push_back(dsu.get(id1) == dsu.get(id2));
    }
  }
  reverse((ans).begin(), (ans).end());
  for (int x : ans) cout << x << "\n";
  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 IINF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = numeric_limits<double>::infinity();
const double DNAN = numeric_limits<double>::quiet_NaN();
const double EPS = 1e-9;
const double PI = acos((double)-1.0);
const int DX[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int DY[] = {0, 1, 0, -1, 1, -1, -1, 1};
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long sqr(long long x) { return x * x; }
long long sqr(int x) { return (long long)x * x; }
double sqr(double x) { return x * x; }
mt19937 mmtw(960172);
long long rnd(long long x, long long y) {
  static uniform_int_distribution<long long> d;
  return d(mmtw) % (y - x + 1) + x;
}
template <typename T>
T& updMin(T& a, T const& b) {
  if (b < a) a = b;
  return a;
}
template <typename T>
T& updMax(T& a, T const& b) {
  if (a < b) a = b;
  return a;
}
long long divFloor(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? a / b : (a - b + 1) / b;
}
long long divCeil(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? (a + b - 1) / b : a / b;
}
long long divFloorS(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? (a + b - 1) / b - 1 : a / b - 1;
}
long long divCeilS(long long a, long long b) {
  if (b < 0) {
    a = -a;
    b = -b;
  }
  return a >= 0 ? a / b + 1 : (a - b + 1) / b + 1;
}
template <typename K, typename V>
V getOrDef(map<K, V> const& a, K const& k, V const& def = V()) {
  auto it = a.find(k);
  return it == a.end() ? def : it->second;
}
template <typename K, typename V>
V getOrDef(unordered_map<K, V> const& a, K const& k, V const& def = V()) {
  auto it = a.find(k);
  return it == a.end() ? def : it->second;
}
template <typename A, typename B>
istream& operator>>(istream& in, pair<A, B>& p) {
  return in >> p.first >> p.second;
}
template <typename A, typename B>
ostream& operator<<(ostream& out, pair<A, B> const& p) {
  return out << p.first << " " << p.second;
}
template <typename T>
istream& operator>>(istream& in, vector<T>& a) {
  for (T& x : a) in >> x;
  return in;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> const& a) {
  bool f = true;
  for (T const& x : a) {
    if (!f) out << " ";
    f = false;
    out << x;
  }
  return out;
}
template <typename T>
bool isZero(T const& x) {
  return x == T(0);
}
bool isZero(float x) { return abs(x) < EPS; }
bool isZero(double x) { return abs(x) < EPS; }
bool isZero(long double x) { return abs(x) < EPS; }
template <typename T>
int sgn(T const& x) {
  if (isZero(x)) return 0;
  return x > 0 ? 1 : -1;
}
struct Node {
  long long cl, cr;
  Node* l = nullptr;
  Node* r = nullptr;
  int id = -1;
  bool leaf = true;
  bool destroyed = 0;
  Node(long long cl, long long cr) : cl(cl), cr(cr) {}
};
struct Query {
  bool destroy;
  long long a, b;
};
void down1(long long l, long long r, Node* c) {
  if (l >= c->cr || c->cl >= r) return;
  if (l <= c->cl && c->cr <= r) {
    assert(c->leaf);
    c->destroyed = 1;
    return;
  }
  if (c->leaf) {
    assert(!c->destroyed);
    c->leaf = 0;
    long long mid = (c->cl + c->cr) / 2;
    c->l = new Node(c->cl, mid);
    c->r = new Node(mid, c->cr);
  }
  down1(l, r, c->l);
  down1(l, r, c->r);
}
vector<Node*> leafs;
vector<long long> cls;
void dfs2(Node* c) {
  if (c->leaf) {
    leafs.push_back(c);
    cls.push_back(c->cl);
  } else {
    dfs2(c->l);
    dfs2(c->r);
  }
}
struct DSU {
  vector<int> p;
  DSU() = default;
  DSU(int n) : p(n, -1) {}
  int get(int v) { return p[v] == -1 ? v : p[v] = get(p[v]); }
  bool merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return false;
    p[y] = x;
    return true;
  }
} dsu;
int k;
Node* root;
int main() {
  ios::sync_with_stdio(false);
  int qn;
  cin >> k >> qn;
  long long n = 1LL << k;
  vector<Query> qs;
  root = new Node(0, n);
  for (int i = 0; i < qn; ++i) {
    string type;
    long long a, b;
    cin >> type >> a >> b;
    if (type == "block") {
      qs.push_back({1, a, b + 1});
      down1(a, b + 1, root);
    } else {
      qs.push_back({0, a, b});
    }
  }
  dfs2(root);
  for (int i = 0; i < ((int)((leafs).size())); ++i) leafs[i]->id = i;
  dsu = DSU(((int)((leafs).size())));
  for (int id = 0; id < ((int)((leafs).size())); ++id) {
    Node* c = leafs[id];
    if (c->destroyed) continue;
    long long len = c->cr - c->cl;
    for (int i = 0; i < k; ++i) {
      if ((1LL << i) < len) continue;
      long long nl = c->cl ^ (1LL << i);
      long long nr = nl + len;
      int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
      while (j < ((int)((cls).size())) && cls[j] < nr) {
        if (!leafs[j]->destroyed) dsu.merge(id, j);
        j++;
      }
    }
  }
  vector<int> ans;
  reverse((qs).begin(), (qs).end());
  for (Query const& q : qs) {
    if (q.destroy) {
      int id1 = lower_bound((cls).begin(), (cls).end(), q.a) - cls.begin();
      int id2 = lower_bound((cls).begin(), (cls).end(), q.b) - cls.begin();
      for (int id = id1; id < id2; ++id) {
        Node* c = leafs[id];
        c->destroyed = false;
        long long len = c->cr - c->cl;
        for (int i = 0; i < k; ++i) {
          if ((1LL << i) < len) continue;
          long long nl = c->cl ^ (1LL << i);
          long long nr = nl + len;
          int j = upper_bound((cls).begin(), (cls).end(), nl) - cls.begin() - 1;
          while (j < ((int)((cls).size())) && cls[j] < nr) {
            if (!leafs[j]->destroyed) dsu.merge(id, j);
            j++;
          }
        }
      }
    } else {
      int id1 = upper_bound((cls).begin(), (cls).end(), q.a) - cls.begin() - 1;
      int id2 = upper_bound((cls).begin(), (cls).end(), q.b) - cls.begin() - 1;
      ans.push_back(dsu.get(id1) == dsu.get(id2));
    }
  }
  reverse((ans).begin(), (ans).end());
  for (int x : ans) cout << x << "\n";
  return 0;
}

```