You are given an undirected graph with n vertices numbered from 1 to n. Initially there are no edges.

You are asked to perform some queries on the graph. Let last be the answer to the latest query of the second type, it is set to 0 before the first such query. Then the queries are the following:

  * 1~x~y (1 ≤ x, y ≤ n, x ≠ y) — add an undirected edge between the vertices (x + last - 1)~mod~n + 1 and (y + last - 1)~mod~n + 1 if it doesn't exist yet, otherwise remove it; 
  * 2~x~y (1 ≤ x, y ≤ n, x ≠ y) — check if there exists a path between the vertices (x + last - 1)~mod~n + 1 and (y + last - 1)~mod~n + 1, which goes only through currently existing edges, and set last to 1 if so and 0 otherwise. 



Good luck!

Input

The first line contains two integer numbers n and m (2 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices and the number of queries, respectively.

Each of the following m lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.

Output

Print a string, consisting of characters '0' and '1'. The i-th character should be the answer to the i-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.

Examples

Input


5 9
1 1 2
1 1 3
2 3 2
1 2 4
2 3 4
1 2 4
2 3 4
1 1 3
2 4 3


Output


1010


Input


3 9
1 1 2
1 2 3
1 3 1
2 1 3
1 3 2
2 2 3
1 1 2
2 1 2
2 1 2


Output


1101

Note

The converted queries in the first example are:

  * 1 1 2 
  * 1 1 3 
  * 2 3 2 
  * 1 3 5 
  * 2 4 5 
  * 1 2 4 
  * 2 3 4 
  * 1 2 4 
  * 2 5 4 



The converted queries in the second example are:

  * 1 1 2 
  * 1 2 3 
  * 1 3 1 
  * 2 1 3 
  * 1 1 3 
  * 2 3 1 
  * 1 2 3 
  * 2 2 3 
  * 2 1 2 
#include <bits/stdc++.h>
using namespace std;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = (lookup_value & 15) + '0';
    number_buffer[length++] = (lookup_value >> 4) + '0';
  }
  if (number != 0 || length == 0) write_char(number + '0');
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
struct union_find {
  vector<int> p;
  vector<pair<int, int>> s;
  union_find(int n) : p(n, -1) { s.reserve(2 * n); }
  bool join(int u, int v) {
    if ((u = root(u)) == (v = root(v))) return false;
    if (p[u] > p[v]) swap(u, v);
    s.emplace_back(u, p[u]);
    s.emplace_back(v, p[v]);
    p[u] += p[v];
    p[v] = u;
    return true;
  }
  void undo(int k) {
    for (int it = 2 * k; it--;)
      p[s.back().first] = s.back().second, s.pop_back();
  }
  int root(int u) { return p[u] < 0 ? u : root(p[u]); }
};
struct query {
  int id, t, x, y;
};
struct info {
  int x, y, l, r, eid;
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  IO::init();
  int n, m;
  IO::read_int(n, m);
  vector<query> queries(m);
  map<pair<int, int>, vector<int>> times;
  for (auto &i : queries) {
    IO::read_int(i.t, i.x, i.y);
    i.id = &i - &queries[0];
    if (i.t == 1) {
      if (i.x % n > i.y % n) swap(i.x, i.y);
      times[{i.x % n, i.y % n}].push_back(~i.id);
      if (i.x > i.y) swap(i.x, i.y);
      times[{i.x - 1, i.y - 1}].push_back(i.id);
    }
  }
  auto get = [&](int x) {
    if (x < 0) return ~x;
    return x;
  };
  vector<bool> obliged(m);
  vector<info> v;
  int eid = 0;
  for (auto &i : times) {
    int sz = i.second.size();
    i.second.push_back(m);
    for (int j = 0; j < sz; ++j) {
      if (get(i.second[j]) == get(i.second[j + 1])) {
        ++j;
        obliged[i.second[j]] = true;
      }
      v.push_back(
          {i.first.first, i.first.second, i.second[j], i.second[j + 1], eid});
    }
    ++eid;
  }
  union_find uf(n);
  vector<bool> ans(m), alive(eid);
  auto state = [&](int x) {
    if (x < 0 || !ans[x]) return false;
    return true;
  };
  function<void(int, int, vector<info> &)> f = [&](int l, int r,
                                                   vector<info> &q) {
    int md = (l + r) >> 1;
    vector<info> left, right;
    int undo = 0;
    for (auto i : q) {
      if (get(i.l) <= l && r <= get(i.r)) {
        bool take = (state(get(i.l) - 1) == (i.l < 0) || obliged[get(i.l)]) &&
                    l == get(i.l);
        if (take) {
          if (!alive[i.eid])
            undo += uf.join(i.x, i.y), alive[i.eid] = true;
          else
            alive[i.eid] = false;
        } else {
          if (alive[i.eid]) undo += uf.join(i.x, i.y);
        }
      } else {
        if (get(i.l) < md) left.push_back(i);
        if (md < get(i.r)) right.push_back(i);
      }
    }
    if (l + 1 != r) {
      f(l, md, left);
      f(md, r, right);
    } else {
      if (queries[l].t == 2) {
        bool w = !state(l - 1);
        ans[l] =
            uf.root((queries[l].x - w) % n) == uf.root((queries[l].y - w) % n);
        cout << ans[l];
      } else
        ans[l] = state(l - 1);
    }
    uf.undo(undo);
  };
  f(0, m, v);
  cout << "\n";
  return 0;
}
