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>
long long int const MOD = 1000000007;
long long int const N = 1000005;
long long int const LN = 20;
long long int const inf = 8e18;
using namespace std;
long long int n, m, a[N];
struct query {
  long long int tp, x, y;
  long long int e0, e1;
};
long long int const Block = 400;
query q[N];
pair<long long int, long long int> e[N];
map<pair<long long int, long long int>, long long int> mp;
long long int rev[N];
long long int stk[N], top = 0;
long long int val[N];
struct dsu {
  long long int id[N];
  long long int rk[N];
  long long int p[N];
  dsu() {
    for (long long int i = 0; i < N; i++) {
      rk[i] = 1, p[i] = 0;
      id[i] = i;
    }
  }
  void ini(long long int n) {
    for (long long int i = 0; i <= n; i++) {
      rk[i] = 1, p[i] = 0;
      id[i] = i;
    }
  }
  long long int Find(long long int x) {
    while (id[x] != x) {
      x = id[x];
    }
    return x;
  }
  void uni(long long int x, long long int y) {
    x = Find(x);
    y = Find(y);
    if (x == y) {
      return;
    }
    if (rk[x] > rk[y]) {
      swap(x, y);
    }
    stk[++top] = -y;
    val[top] = rk[y];
    rk[y] += rk[x];
    id[x] = y;
    stk[++top] = x;
    val[top] = x;
  }
  void restore(long long int k) {
    while (top > k) {
      if (stk[top] < 0) {
        rk[-stk[top]] = val[top];
      } else {
        id[stk[top]] = stk[top];
      }
      top--;
    }
  }
} wup;
long long int get_edge(pair<long long int, long long int> ee) {
  if (mp.find(ee) == mp.end()) {
    long long int k = mp.size();
    e[k + 1] = ee;
    mp[ee] = k + 1;
  }
  return mp[ee];
}
long long int ans[N];
long long int vis[N];
long long int on[N];
set<long long int> curr;
void build(long long int idx) {
  for (long long int i = 0; i <= mp.size(); i++) {
    vis[i] = on[i] = 0;
  }
  wup.ini(n);
  for (long long int i = 0; i < idx; i++) {
    if (q[i].tp == 1) {
      long long int idx = (ans[i] ? q[i].e1 : q[i].e0);
      vis[idx] = 1;
      on[idx] ^= 1;
    }
  }
  long long int r = min(m, idx + Block - 1);
  for (long long int i = idx; i <= r; i++) {
    if (q[i].tp == 1) {
      vis[q[i].e0] = vis[q[i].e1] = 0;
    }
  }
  curr.clear();
  top = 0;
  for (long long int i = 0; i < idx; i++) {
    if (q[i].tp == 1) {
      long long int idx = (ans[i] ? q[i].e1 : q[i].e0);
      if (vis[idx] && on[idx]) {
        on[idx] = 0;
        wup.uni(e[idx].first, e[idx].second);
      } else if (!vis[idx] && on[idx]) {
        on[idx] = 0;
        curr.insert(idx);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (long long int i = 0; i < m; i++) {
    cin >> q[i].tp >> q[i].x >> q[i].y;
    pair<long long int, long long int> e0 = {(q[i].x - 1 + n) % n + 1,
                                             (q[i].y - 1 + n) % n + 1};
    pair<long long int, long long int> e1 = {(q[i].x + n) % n + 1,
                                             (q[i].y + n) % n + 1};
    if (e0.first > e0.second) {
      swap(e0.first, e0.second);
    }
    if (e1.first > e1.second) {
      swap(e1.first, e1.second);
    }
    q[i].e0 = get_edge(e0);
    q[i].e1 = get_edge(e1);
  }
  ans[0] = 0;
  long long int wy = 0;
  for (long long int i = 0; i < m; i++) {
    if (i % Block == 0) {
      build(i);
      wy = top;
    }
    long long int x = (q[i].x + ans[i] - 1 + n) % n + 1;
    long long int y = (q[i].y + ans[i] - 1 + n) % n + 1;
    if (x > y) {
      swap(x, y);
    }
    if (q[i].tp == 1) {
      wup.restore(wy);
      long long int idx = get_edge({x, y});
      if (curr.find(idx) == curr.end()) {
        curr.insert(idx);
      } else {
        curr.erase(idx);
      }
      ans[i + 1] = ans[i];
    } else {
      for (auto w : curr) {
        wup.uni(e[w].first, e[w].second);
      }
      if (wup.Find(x) == wup.Find(y)) {
        ans[i + 1] = 1;
      } else {
        ans[i + 1] = 0;
      }
    }
  }
  for (long long int i = 0; i < m; i++) {
    if (q[i].tp == 2) {
      cout << ans[i + 1];
    }
  }
  return 0;
}
