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;
const long long MOD = 1e9 + 7;
template <typename T>
void chmin(T &a, T b) {
  if (a > b) a = b;
}
template <typename T>
void chmax(T &a, T b) {
  if (a < b) a = b;
}
template <typename T>
void add(T &a, T b) {
  a += b;
  if (a < 0) a += MOD;
  if (a >= MOD) a -= MOD;
}
void FastIn(int &T) {
  char C;
  bool F = 0;
  for (; C = getchar(), C < '0' || C > '9';)
    if (C == '-') F = 1;
  for (T = C - '0'; C = getchar(), C >= '0' && C <= '9'; T = T * 10 + C - '0')
    ;
  F && (T = -T);
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}
long long lin() {
  long long x;
  scanf("%lld", &x);
  return x;
}
double din() {
  double x;
  scanf("%lf", &x);
  return x;
}
long long p2[63];
void initP2() {
  p2[0] = 1;
  for (int i = (1); i <= (62); ++i) {
    p2[i] = p2[i - 1] * 2;
  }
}
int countBitsBaseB(long long n, long long b) {
  if (n == 0) return 1;
  int ret = 0;
  while (n) {
    ret++;
    n /= b;
  }
  return ret;
}
int count1(long long n) {
  int ret = 0;
  while (n) {
    ret += n & 1;
    n >>= 1;
  }
  return ret;
}
long long c[1024][1024] = {0};
void initC() {
  for (int i = 0; i < (1024); ++i) {
    for (int j = 0; j < (i + 1); ++j) {
      if (j == 0 || j == i) {
        c[i][j] = 1;
      } else {
        c[i][j] = c[i - 1][j - 1];
        add(c[i][j], c[i - 1][j]);
      }
    }
  }
}
bool IsPrime(int n) {
  if (n < 2) return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void init() {
  initP2();
  initC();
}
const unsigned INVALID = 2000000001;
struct CMD {
  int cmd, x, y;
} q[(int)(2e5 + 10)];
struct DSU {
  struct INFO {
    int x, f, h;
    INFO() {}
    INFO(int x_, int f_, int h_) : x(x_), f(f_), h(h_) {}
  };
  int f[(int)(2e5 + 10)];
  int h[(int)(2e5 + 10)];
  INFO stk[(int)(2e5 + 10) << 1];
  int stkSize = 0;
  void init(int n) {
    for (int i = (1); i <= (n); ++i) {
      f[i] = i;
      h[i] = 1;
    }
    stkSize = 0;
  }
  int find(int x) { return x == f[x] ? x : find(f[x]); }
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return;
    }
    if (h[x] < h[y]) {
      stk[stkSize++] = (INFO(x, f[x], h[x]));
      f[x] = y;
    } else if (h[y] < h[x]) {
      stk[stkSize++] = (INFO(y, f[y], h[y]));
      f[y] = x;
    } else {
      stk[stkSize++] = (INFO(x, f[x], h[x]));
      stk[stkSize++] = (INFO(y, f[y], h[y]));
      f[x] = y;
      h[y]++;
    }
  }
  void undo(int size) {
    while (stkSize > size) {
      pop();
    }
  }

 private:
  void pop() {
    stkSize--;
    auto info = stk[stkSize];
    int x = info.x;
    f[x] = info.f;
    h[x] = info.h;
  }
} dsu;
const int BLOCK = 5000;
int last[(int)(2e5 + 10)];
pair<int, int> GetEdge(int x, int y, int der, int n) {
  x += der - 1;
  if (x >= n) x -= n;
  y += der - 1;
  if (y >= n) y -= n;
  if (x > y) swap(x, y);
  return make_pair(x + 1, y + 1);
}
void Switch(const pair<int, int> &edge, set<pair<int, int>> &edges) {
  if (edges.find(edge) != edges.end()) {
    edges.erase(edge);
  } else {
    edges.insert(edge);
  }
}
int main() {
  init();
  int n = in(), m = in();
  for (int i = (1); i <= (m); ++i) {
    q[i].cmd = in();
    q[i].x = in();
    q[i].y = in();
  }
  last[0] = 0;
  for (int start = 1; start <= m; start += BLOCK) {
    int end = start + BLOCK - 1;
    if (end > m) {
      end = m;
    }
    set<pair<int, int>> nowEdges;
    nowEdges.clear();
    for (int i0 = (start); i0 <= (end); ++i0) {
      nowEdges.insert(GetEdge(q[i0].x, q[i0].y, 0, n));
      nowEdges.insert(GetEdge(q[i0].x, q[i0].y, 1, n));
    }
    set<pair<int, int>> possible;
    possible.clear();
    set<pair<int, int>> impossible;
    impossible.clear();
    for (int i1 = (1); i1 <= (start - 1); ++i1) {
      if (q[i1].cmd == 2) {
        continue;
      }
      auto edge0 = GetEdge(q[i1].x, q[i1].y, last[i1 - 1], n);
      if (nowEdges.find(edge0) == nowEdges.end()) {
        Switch(edge0, impossible);
      } else {
        Switch(edge0, possible);
      }
    }
    dsu.init(n);
    for (auto edge1 : impossible) {
      dsu.merge(edge1.first, edge1.second);
    }
    for (int i2 = (start); i2 <= (end); ++i2) {
      if (q[i2].cmd == 1) {
        last[i2] = last[i2 - 1];
        Switch(GetEdge(q[i2].x, q[i2].y, last[i2 - 1], n), possible);
        continue;
      } else {
        const int top = dsu.stkSize;
        for (auto edge1 : possible) {
          dsu.merge(edge1.first, edge1.second);
        }
        auto queryEdge = GetEdge(q[i2].x, q[i2].y, last[i2 - 1], n);
        last[i2] = dsu.find(queryEdge.first) == dsu.find(queryEdge.second);
        putchar('0' + last[i2]);
        dsu.undo(top);
      }
    }
  }
  cout << endl;
  return 0;
}
