#include <bits/stdc++.h>
using namespace std;
void per() { cerr << endl; }
template <typename Head, typename... Tail>
void per(Head H, Tail... T) {
  cerr << H << ' ';
  per(T...);
}
template <class T>
bool uin(T& a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T& a, T b) {
  return a < b ? (a = b, true) : false;
}
template <class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& a) {
  return out << "(" << a.first << ", " << a.second << ")";
}
template <class U, class V>
istream& operator>>(istream& in, pair<U, V>& a) {
  return in >> a.first >> a.second;
}
template <typename W,
          typename T = typename enable_if<!is_same<W, string>::value,
                                          typename W::value_type>::type>
ostream& operator<<(ostream& out, const W& v) {
  out << "{ ";
  for (const auto& first : v) out << first << ", ";
  return out << '}';
}
template <class T>
void readArr(T from, T to) {
  for (auto i = from; i != to; ++i) cin >> *i;
}
mt19937 mrand(1337);
unsigned int myRand32() { return mrand() & (unsigned int)(-1); }
unsigned long long myRand64() {
  return ((unsigned long long)myRand32() << 32) ^ myRand32();
}
const int mod = 1000000007;
void add(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
void dec(int& a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
int mult(int a, int b) { return a * (long long)b % mod; }
int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
struct Vertex {
  int l;
  int r;
  int father;
  int cnt;
};
Vertex rmq[4000007];
int ptr = 0;
vector<int> want[4000007];
int create(int vertex) {
  rmq[ptr++] = {-1, -1, vertex, 0};
  want[ptr - 1] = {};
  return ptr - 1;
}
void go(int vertex, long long l, long long r, long long l1, long long r1) {
  if (l1 >= r1) return;
  if (l == l1 && r == r1) {
    rmq[vertex].cnt = 1;
    return;
  }
  if (rmq[vertex].l == -1) {
    rmq[vertex].l = create(vertex);
  }
  if (rmq[vertex].r == -1) {
    rmq[vertex].r = create(vertex);
  }
  long long mid = (l + r) / 2;
  go(rmq[vertex].l, l, mid, l1, min(r1, mid));
  go(rmq[vertex].r, mid, r, max(l1, mid), r1);
  rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
}
struct Node {
  int p, r, f;
};
struct DSU {
  static const int SZ = 10000007;
  Node t[SZ];
  DSU() { reset(SZ); }
  void reset(int n) {
    for (int i = 0; i < n; ++i) {
      t[i].p = i;
      t[i].r = 0;
      t[i].f = 1;
    }
  }
  int get(int v) {
    if (t[v].p == v) return v;
    return t[v].p = get(t[v].p);
  }
  int get_func(int v) { return t[get(v)].f; }
  void merge(int a, int b) {
    a = get(a), b = get(b);
    if (a != b) {
      if (t[a].r < t[b].r) swap(a, b);
      t[b].p = a;
      t[a].f += t[b].f;
      if (t[a].r == t[b].r) ++t[a].r;
    }
  }
};
DSU dsu;
bool good(int vertex) {
  if (vertex == -1) return false;
  if (rmq[vertex].cnt) return false;
  return true;
}
void restore(int vertex) {
  if (good(rmq[vertex].father)) dsu.merge(vertex, rmq[vertex].father);
  if (good(rmq[vertex].l)) dsu.merge(vertex, rmq[vertex].l);
  if (good(rmq[vertex].r)) dsu.merge(vertex, rmq[vertex].r);
  for (auto to : want[vertex]) dsu.merge(vertex, to);
  int W = vertex;
  vector<int> bits;
  while (true) {
    int t = rmq[vertex].father;
    if (t == -1) break;
    if (rmq[t].l == vertex)
      bits.push_back(0);
    else
      bits.push_back(1);
    vertex = t;
  }
  reverse(bits.begin(), bits.end());
  int start = 0;
  for (int i = 0; i < bits.size() && start != -1; ++i) {
    bits[i] ^= 1;
    int now = start;
    for (int j = i; j < bits.size(); ++j) {
      int first = bits[j];
      if (first == 0) {
        if (rmq[now].l == -1) {
          break;
        }
        now = rmq[now].l;
      } else {
        if (rmq[now].r == -1) {
          break;
        }
        now = rmq[now].r;
      }
    }
    if (good(now)) {
      dsu.merge(W, now);
    } else
      want[now].push_back(W);
    bits[i] ^= 1;
    if (bits[i] == 0) start = rmq[start].l;
    if (bits[i] == 1) start = rmq[start].r;
  }
}
void go_back(int vertex, long long l, long long r, long long l1, long long r1) {
  if (l1 >= r1) return;
  if (l == l1 && r == r1) {
    rmq[vertex].cnt = 0;
    restore(vertex);
    return;
  }
  long long mid = (l + r) / 2;
  go_back(rmq[vertex].l, l, mid, l1, min(r1, mid));
  go_back(rmq[vertex].r, mid, r, max(l1, mid), r1);
  int W = rmq[vertex].cnt;
  rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
  if (rmq[vertex].cnt == 0 && W != 0) restore(vertex);
}
int n, m;
int gg(long long first) {
  int now = 0;
  for (int i = n - 1; i >= 0; --i) {
    int t = (((1LL << i) & first) > 0);
    if (t == 0) {
      if (rmq[now].l == -1) return now;
      now = rmq[now].l;
    } else {
      if (rmq[now].r == -1) return now;
      now = rmq[now].r;
    }
  }
  return now;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  create(-1);
  rmq[0].l = create(0);
  rmq[0].r = create(0);
  vector<tuple<int, long long, long long> > queries;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    string s;
    cin >> s;
    if (s == "ask") {
      long long l, r;
      cin >> l >> r;
      queries.push_back(make_tuple(0, l, r));
    } else {
      long long l, r;
      cin >> l >> r;
      queries.push_back(make_tuple(1, l, r));
      go(0, 0, (1ll << n), l, r + 1);
    }
  }
  vector<int> ans;
  dsu.reset(ptr);
  for (int i = 0; i < ptr; ++i) {
    if (!rmq[i].cnt) {
      restore(i);
    }
  }
  reverse(queries.begin(), queries.end());
  for (auto first : queries) {
    int tp = get<0>(first);
    long long l = get<1>(first);
    long long r = get<2>(first);
    if (tp == 1) {
      go_back(0, 0, (1ll << n), l, r + 1);
    } else {
      int A = gg(l), B = gg(r);
      if (dsu.get(A) == dsu.get(B) && !rmq[A].cnt && !rmq[B].cnt)
        ans.push_back(1);
      else
        ans.push_back(0);
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto first : ans) cout << first << '\n';
}

### Prompt

Create a solution in cpp for 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;
void per() { cerr << endl; }
template <typename Head, typename... Tail>
void per(Head H, Tail... T) {
  cerr << H << ' ';
  per(T...);
}
template <class T>
bool uin(T& a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T& a, T b) {
  return a < b ? (a = b, true) : false;
}
template <class U, class V>
ostream& operator<<(ostream& out, const pair<U, V>& a) {
  return out << "(" << a.first << ", " << a.second << ")";
}
template <class U, class V>
istream& operator>>(istream& in, pair<U, V>& a) {
  return in >> a.first >> a.second;
}
template <typename W,
          typename T = typename enable_if<!is_same<W, string>::value,
                                          typename W::value_type>::type>
ostream& operator<<(ostream& out, const W& v) {
  out << "{ ";
  for (const auto& first : v) out << first << ", ";
  return out << '}';
}
template <class T>
void readArr(T from, T to) {
  for (auto i = from; i != to; ++i) cin >> *i;
}
mt19937 mrand(1337);
unsigned int myRand32() { return mrand() & (unsigned int)(-1); }
unsigned long long myRand64() {
  return ((unsigned long long)myRand32() << 32) ^ myRand32();
}
const int mod = 1000000007;
void add(int& a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
void dec(int& a, int b) {
  a -= b;
  if (a < 0) a += mod;
}
int mult(int a, int b) { return a * (long long)b % mod; }
int bp(int a, int b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
struct Vertex {
  int l;
  int r;
  int father;
  int cnt;
};
Vertex rmq[4000007];
int ptr = 0;
vector<int> want[4000007];
int create(int vertex) {
  rmq[ptr++] = {-1, -1, vertex, 0};
  want[ptr - 1] = {};
  return ptr - 1;
}
void go(int vertex, long long l, long long r, long long l1, long long r1) {
  if (l1 >= r1) return;
  if (l == l1 && r == r1) {
    rmq[vertex].cnt = 1;
    return;
  }
  if (rmq[vertex].l == -1) {
    rmq[vertex].l = create(vertex);
  }
  if (rmq[vertex].r == -1) {
    rmq[vertex].r = create(vertex);
  }
  long long mid = (l + r) / 2;
  go(rmq[vertex].l, l, mid, l1, min(r1, mid));
  go(rmq[vertex].r, mid, r, max(l1, mid), r1);
  rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
}
struct Node {
  int p, r, f;
};
struct DSU {
  static const int SZ = 10000007;
  Node t[SZ];
  DSU() { reset(SZ); }
  void reset(int n) {
    for (int i = 0; i < n; ++i) {
      t[i].p = i;
      t[i].r = 0;
      t[i].f = 1;
    }
  }
  int get(int v) {
    if (t[v].p == v) return v;
    return t[v].p = get(t[v].p);
  }
  int get_func(int v) { return t[get(v)].f; }
  void merge(int a, int b) {
    a = get(a), b = get(b);
    if (a != b) {
      if (t[a].r < t[b].r) swap(a, b);
      t[b].p = a;
      t[a].f += t[b].f;
      if (t[a].r == t[b].r) ++t[a].r;
    }
  }
};
DSU dsu;
bool good(int vertex) {
  if (vertex == -1) return false;
  if (rmq[vertex].cnt) return false;
  return true;
}
void restore(int vertex) {
  if (good(rmq[vertex].father)) dsu.merge(vertex, rmq[vertex].father);
  if (good(rmq[vertex].l)) dsu.merge(vertex, rmq[vertex].l);
  if (good(rmq[vertex].r)) dsu.merge(vertex, rmq[vertex].r);
  for (auto to : want[vertex]) dsu.merge(vertex, to);
  int W = vertex;
  vector<int> bits;
  while (true) {
    int t = rmq[vertex].father;
    if (t == -1) break;
    if (rmq[t].l == vertex)
      bits.push_back(0);
    else
      bits.push_back(1);
    vertex = t;
  }
  reverse(bits.begin(), bits.end());
  int start = 0;
  for (int i = 0; i < bits.size() && start != -1; ++i) {
    bits[i] ^= 1;
    int now = start;
    for (int j = i; j < bits.size(); ++j) {
      int first = bits[j];
      if (first == 0) {
        if (rmq[now].l == -1) {
          break;
        }
        now = rmq[now].l;
      } else {
        if (rmq[now].r == -1) {
          break;
        }
        now = rmq[now].r;
      }
    }
    if (good(now)) {
      dsu.merge(W, now);
    } else
      want[now].push_back(W);
    bits[i] ^= 1;
    if (bits[i] == 0) start = rmq[start].l;
    if (bits[i] == 1) start = rmq[start].r;
  }
}
void go_back(int vertex, long long l, long long r, long long l1, long long r1) {
  if (l1 >= r1) return;
  if (l == l1 && r == r1) {
    rmq[vertex].cnt = 0;
    restore(vertex);
    return;
  }
  long long mid = (l + r) / 2;
  go_back(rmq[vertex].l, l, mid, l1, min(r1, mid));
  go_back(rmq[vertex].r, mid, r, max(l1, mid), r1);
  int W = rmq[vertex].cnt;
  rmq[vertex].cnt = rmq[rmq[vertex].l].cnt + rmq[rmq[vertex].r].cnt;
  if (rmq[vertex].cnt == 0 && W != 0) restore(vertex);
}
int n, m;
int gg(long long first) {
  int now = 0;
  for (int i = n - 1; i >= 0; --i) {
    int t = (((1LL << i) & first) > 0);
    if (t == 0) {
      if (rmq[now].l == -1) return now;
      now = rmq[now].l;
    } else {
      if (rmq[now].r == -1) return now;
      now = rmq[now].r;
    }
  }
  return now;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  create(-1);
  rmq[0].l = create(0);
  rmq[0].r = create(0);
  vector<tuple<int, long long, long long> > queries;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    string s;
    cin >> s;
    if (s == "ask") {
      long long l, r;
      cin >> l >> r;
      queries.push_back(make_tuple(0, l, r));
    } else {
      long long l, r;
      cin >> l >> r;
      queries.push_back(make_tuple(1, l, r));
      go(0, 0, (1ll << n), l, r + 1);
    }
  }
  vector<int> ans;
  dsu.reset(ptr);
  for (int i = 0; i < ptr; ++i) {
    if (!rmq[i].cnt) {
      restore(i);
    }
  }
  reverse(queries.begin(), queries.end());
  for (auto first : queries) {
    int tp = get<0>(first);
    long long l = get<1>(first);
    long long r = get<2>(first);
    if (tp == 1) {
      go_back(0, 0, (1ll << n), l, r + 1);
    } else {
      int A = gg(l), B = gg(r);
      if (dsu.get(A) == dsu.get(B) && !rmq[A].cnt && !rmq[B].cnt)
        ans.push_back(1);
      else
        ans.push_back(0);
    }
  }
  reverse(ans.begin(), ans.end());
  for (auto first : ans) cout << first << '\n';
}

```