#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug &operator<<(const c &) {
    return *this;
  }
};
struct segment {
  long long a, b;
  int t;
  int id;
  segment(long long _a = 0, long long _b = 0, int _t = 0, int _id = 0) {
    a = _a;
    b = _b;
    t = _t;
    id = _id;
  }
};
struct query {
  long long a, b;
  int t;
  query(long long _a = 0, long long _b = 0, int _t = 0) {
    a = _a;
    b = _b;
    t = _t;
  }
};
const int MAXN = 51;
const int MAXM = 5e4 + 10;
vector<segment> segments;
vector<query> queries;
vector<int> gr[2 * MAXN * MAXM];
int t[2 * MAXN * MAXM];
int card[2 * MAXN * MAXM];
int no = 0;
vector<segment> rec(long long l, long long r, vector<segment> &segments) {
  vector<segment> s;
  s.reserve(segments.size() * 2);
  if (!segments.size()) {
    s.emplace_back(l, r, 1e9, no++);
    return s;
  }
  if (segments.size() == 1 && segments[0].a == l && segments[0].b == r) {
    s.emplace_back(l, r, segments[0].t, no++);
    return s;
  }
  vector<segment> s_left;
  vector<segment> s_right;
  s_left.reserve(segments.size() * 2);
  s_right.reserve(segments.size());
  long long m = l + r >> 1;
  for (auto &x : segments) {
    if (x.b <= m) {
      s_left.emplace_back(x);
    } else if (x.a > m) {
      s_right.emplace_back(x);
    } else {
      s_left.emplace_back(x.a, m, x.t);
      s_right.emplace_back(m + 1, x.b, x.t);
    }
  }
  auto ss_left = rec(l, m, s_left);
  auto ss_right = rec(m + 1, r, s_right);
  int long long = 0, rr = 0;
  long long dif = m + 1 - l;
  while (long long < ss_left.size() && rr < ss_right.size()) {
    if ((ss_left[long long].a >= ss_right[rr].a - dif &&
         ss_left[long long].a <= ss_right[rr].b - dif) ||
        (ss_right[rr].a >= ss_left[long long].a + dif &&
         ss_right[rr].a <= ss_left[long long].b + dif)) {
      gr[ss_left[long long].id].emplace_back(ss_right[rr].id);
      gr[ss_right[rr].id].emplace_back(ss_left[long long].id);
    }
    if (ss_left[long long].b <= ss_right[rr].b - dif) {
      ++long long;
    } else {
      ++rr;
    }
  }
  for (auto &x : ss_right) {
    ss_left.emplace_back(x);
  }
  return ss_left;
}
int root(int x) { return x == t[x] ? x : t[x] = root(t[x]); }
void onion(int x, int y) {
  if ((x = root(x)) == (y = root(y))) return;
  if (card[x] < card[y]) swap(x, y);
  t[y] = x;
  card[x] += card[y];
  return;
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    string s;
    long long a, b;
    cin >> s >> a >> b;
    if (s == "ask") {
      queries.emplace_back(a, b, i);
    } else {
      segments.emplace_back(a, b, i, segments.size());
    }
  }
  auto s = rec(0, (1ll << n) - 1, segments);
  for (int i = 0; i < no; ++i) {
    t[i] = i;
    card[i] = 1;
  }
  reverse((queries).begin(), (queries).end());
  vector<int> alive(no);
  auto s_time = s;
  sort((s_time).begin(), (s_time).end(),
       [&](segment &a, segment &b) { return a.t > b.t; });
  auto getSegment = [&](long long a) {
    int ret = 0;
    int l = 0, r = s.size() - 1;
    while (l <= r) {
      int m = l + r >> 1;
      if (s[m].a <= a && s[m].b >= a) return s[m].id;
      if (s[m].b < a) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    assert(false);
    return -1;
  };
  int now = 0;
  vector<int> ans;
  for (auto &x : queries) {
    while (now < s_time.size() && s_time[now].t >= x.t) {
      alive[s_time[now].id] = 1;
      for (auto &x : gr[s_time[now].id]) {
        if (alive[x]) onion(root(s_time[now].id), root(x));
      }
      ++now;
    }
    ans.emplace_back(root(getSegment(x.a)) == root(getSegment(x.b)));
  }
  reverse((ans).begin(), (ans).end());
  for (auto &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;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c *x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug &operator<<(const c &) {
    return *this;
  }
};
struct segment {
  long long a, b;
  int t;
  int id;
  segment(long long _a = 0, long long _b = 0, int _t = 0, int _id = 0) {
    a = _a;
    b = _b;
    t = _t;
    id = _id;
  }
};
struct query {
  long long a, b;
  int t;
  query(long long _a = 0, long long _b = 0, int _t = 0) {
    a = _a;
    b = _b;
    t = _t;
  }
};
const int MAXN = 51;
const int MAXM = 5e4 + 10;
vector<segment> segments;
vector<query> queries;
vector<int> gr[2 * MAXN * MAXM];
int t[2 * MAXN * MAXM];
int card[2 * MAXN * MAXM];
int no = 0;
vector<segment> rec(long long l, long long r, vector<segment> &segments) {
  vector<segment> s;
  s.reserve(segments.size() * 2);
  if (!segments.size()) {
    s.emplace_back(l, r, 1e9, no++);
    return s;
  }
  if (segments.size() == 1 && segments[0].a == l && segments[0].b == r) {
    s.emplace_back(l, r, segments[0].t, no++);
    return s;
  }
  vector<segment> s_left;
  vector<segment> s_right;
  s_left.reserve(segments.size() * 2);
  s_right.reserve(segments.size());
  long long m = l + r >> 1;
  for (auto &x : segments) {
    if (x.b <= m) {
      s_left.emplace_back(x);
    } else if (x.a > m) {
      s_right.emplace_back(x);
    } else {
      s_left.emplace_back(x.a, m, x.t);
      s_right.emplace_back(m + 1, x.b, x.t);
    }
  }
  auto ss_left = rec(l, m, s_left);
  auto ss_right = rec(m + 1, r, s_right);
  int long long = 0, rr = 0;
  long long dif = m + 1 - l;
  while (long long < ss_left.size() && rr < ss_right.size()) {
    if ((ss_left[long long].a >= ss_right[rr].a - dif &&
         ss_left[long long].a <= ss_right[rr].b - dif) ||
        (ss_right[rr].a >= ss_left[long long].a + dif &&
         ss_right[rr].a <= ss_left[long long].b + dif)) {
      gr[ss_left[long long].id].emplace_back(ss_right[rr].id);
      gr[ss_right[rr].id].emplace_back(ss_left[long long].id);
    }
    if (ss_left[long long].b <= ss_right[rr].b - dif) {
      ++long long;
    } else {
      ++rr;
    }
  }
  for (auto &x : ss_right) {
    ss_left.emplace_back(x);
  }
  return ss_left;
}
int root(int x) { return x == t[x] ? x : t[x] = root(t[x]); }
void onion(int x, int y) {
  if ((x = root(x)) == (y = root(y))) return;
  if (card[x] < card[y]) swap(x, y);
  t[y] = x;
  card[x] += card[y];
  return;
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    string s;
    long long a, b;
    cin >> s >> a >> b;
    if (s == "ask") {
      queries.emplace_back(a, b, i);
    } else {
      segments.emplace_back(a, b, i, segments.size());
    }
  }
  auto s = rec(0, (1ll << n) - 1, segments);
  for (int i = 0; i < no; ++i) {
    t[i] = i;
    card[i] = 1;
  }
  reverse((queries).begin(), (queries).end());
  vector<int> alive(no);
  auto s_time = s;
  sort((s_time).begin(), (s_time).end(),
       [&](segment &a, segment &b) { return a.t > b.t; });
  auto getSegment = [&](long long a) {
    int ret = 0;
    int l = 0, r = s.size() - 1;
    while (l <= r) {
      int m = l + r >> 1;
      if (s[m].a <= a && s[m].b >= a) return s[m].id;
      if (s[m].b < a) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    assert(false);
    return -1;
  };
  int now = 0;
  vector<int> ans;
  for (auto &x : queries) {
    while (now < s_time.size() && s_time[now].t >= x.t) {
      alive[s_time[now].id] = 1;
      for (auto &x : gr[s_time[now].id]) {
        if (alive[x]) onion(root(s_time[now].id), root(x));
      }
      ++now;
    }
    ans.emplace_back(root(getSegment(x.a)) == root(getSegment(x.b)));
  }
  reverse((ans).begin(), (ans).end());
  for (auto &x : ans) cout << x << '\n';
  return 0;
}

```