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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
const double PI = 2 * acos(0.0);
const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";
istream &operator>>(istream &in, pair<int, int> &a) {
  in >> a.first >> a.second;
  return in;
}
ostream &operator<<(ostream &out, pair<int, int> &a) {
  out << a.first << ' ' << a.second;
  return out;
}
istream &operator>>(istream &in, pair<double, double> &a) {
  in >> a.first >> a.second;
  return in;
}
ostream &operator<<(ostream &out, pair<double, double> &a) {
  out << a.first << ' ' << a.second;
  return out;
}
template <class T0, class T1>
inline ostream &operator<<(ostream &out, pair<T0, T1> &a) {
  return out << "{" << a.first << ", " << a.second << "}";
}
template <class T0, class T1, class T2>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << "}";
}
template <class T0, class T1, class T2, class T3>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2, T3> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << ", " << get<3>(a) << "}";
}
template <class T>
inline ostream &operator<<(ostream &out, vector<T> &a) {
  out << "[";
  for (int i = 0; i < int(a.size()); ++i)
    out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  return out;
}
void print(int n, int k, vector<tuple<int, int, int, int> > kek) {
  ofstream cout("output.txt");
  cout << n << ' ' << k << '\n';
  for (auto p : kek) {
    int r, x, y, z;
    tie(r, x, y, z) = p;
    cout << x << ' ' << y << ' ' << z << ' ' << r << '\n';
  }
  cout.close();
  exit(0);
}
void smain();
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(12) << fixed;
  smain();
}
const int M1 = 1000000093, p1 = 27162;
const int M2 = 1000000087, p2 = 241;
const double pi = atan2(1, 0) * 2, EPS = 1e-9;
const int pw = 10, N = 2e5 + 10, oo = 1e9 + 100, B = 3000, M = 998244353;
const int NN = 1e4;
const int RND = 37542135;
template <class KEY, class VAL, int N>
struct HashTable {
  pair<KEY, VAL> hmap[NN];
  HashTable(KEY a, KEY b) {
    for (int i = 0; i < int(NN); ++i) hmap[i] = {a, b};
  }
  int has1(KEY v) { return (v ^ RND) % NN; }
  int h1(KEY v, int i) { return (has1(v) + i) % NN; }
  int find(KEY v) {
    int pos, i = 0;
    do {
      pos = h1(v, i);
      if (hmap[pos].first == v) return pos;
      i++;
    } while (hmap[pos].first != -1 && i != NN);
    assert(i != NN);
    return pos;
  }
  VAL get(KEY key) {
    int pos = find(key);
    return hmap[pos].second;
  }
  void set(KEY key, VAL val) {
    int lol = find(key);
    hmap[lol] = {key, val};
  }
};
vector<int> vertices1[N];
vector<int> vertices2[N];
vector<int> bvertices[N];
int used[N], used2[N], TIMER = 1;
long long trans(long long a, long long b) { return (a << 18) | b; }
void dfs(int v, int col) {
  used[v] = col;
  for (int u : vertices2[v]) {
    if (!used[u]) dfs(u, col);
  }
}
void dfs2(int v) {
  used2[v] = TIMER;
  for (int u : bvertices[v]) {
    if (used2[u] != TIMER) dfs2(u);
  }
}
void smain() {
  int n, m;
  cin >> n >> m;
  vector<tuple<int, int, int> > quer(m);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    quer[i] = make_tuple(a, b, c);
  }
  int last = 0;
  vector<int> vertex;
  vertex.reserve(4 * B);
  vector<pair<int, int> > edges;
  edges.reserve(B);
  for (int i = 0; i <= n; ++i) bvertices[i].reserve(B / 10);
  for (int i = 0; i < m; i += B) {
    vertex.clear();
    HashTable<long long, int, NN> abused(-1, 0);
    for (int i = 0; i <= n; ++i) {
      bvertices[i].clear();
      vertices2[i].clear();
      vertices2[i].reserve(((int)((vertices1[i]).size())));
    }
    for (int j = i; j < min(m, i + B); ++j) {
      int a, b, c;
      tie(a, b, c) = quer[j];
      if (a == 1) {
        if (b > c) swap(b, c);
        abused.set(trans(b, c), 1);
        vertex.push_back(b);
        vertex.push_back(c);
        b++, c++;
        if (b == n + 1) b = 1;
        if (c == n + 1) c = 1;
        if (b > c) swap(b, c);
        vertex.push_back(b);
        vertex.push_back(c);
        abused.set(trans(b, c), 1);
      } else {
        vertex.push_back(b);
        vertex.push_back(c);
        b++, c++;
        if (b == n + 1) b = 1;
        if (c == n + 1) c = 1;
        vertex.push_back(b);
        vertex.push_back(c);
      }
    }
    for (int v = 1; v <= n; ++v)
      for (int &u : vertices1[v])
        if (!abused.get(trans(min(v, u), max(v, u)))) {
          vertices2[v].push_back(u);
        }
    int col = 1;
    fill(used, used + N, 0);
    for (auto &v : vertex)
      if (!used[v]) dfs(v, col++);
    edges.clear();
    for (int v = 1; v <= n; ++v)
      for (int &u : vertices1[v])
        if (abused.get(trans(v, u))) {
          if (used[u] != used[v]) {
            bvertices[used[v]].push_back(used[u]);
            bvertices[used[u]].push_back(used[v]);
          }
          edges.push_back(make_pair(min(v, u), (max(v, u))));
        }
    for (int j = i; j < min(m, i + B); ++j) {
      int a, b, c;
      tie(a, b, c) = quer[j];
      if (last) b++, c++;
      if (b == n + 1) b = 1;
      if (c == n + 1) c = 1;
      if (b > c) swap(b, c);
      if (a == 1) {
        if (find(edges.begin(), edges.end(), make_pair(b, (c))) !=
            edges.end()) {
          edges.erase(find(edges.begin(), edges.end(), make_pair(b, (c))));
          if (used[b] != used[c]) {
            bvertices[used[b]].erase(find(bvertices[used[b]].begin(),
                                          bvertices[used[b]].end(), used[c]));
            bvertices[used[c]].erase(find(bvertices[used[c]].begin(),
                                          bvertices[used[c]].end(), used[b]));
          }
        } else {
          edges.push_back(make_pair(b, (c)));
          if (used[b] != used[c]) {
            bvertices[used[b]].push_back(used[c]);
            bvertices[used[c]].push_back(used[b]);
          }
        }
      } else {
        if (used[b] == used[c]) {
          cout << '1';
          last = 1;
        } else {
          dfs2(used[b]);
          if (used2[used[c]] == TIMER) {
            cout << '1';
            last = 1;
          } else {
            cout << '0';
            last = 0;
          }
          TIMER++;
        }
      }
    }
    for (int i = 1; i <= n; ++i) vertices1[i] = vertices2[i];
    for (auto &p : edges) {
      vertices1[p.first].push_back(p.second);
      vertices1[p.second].push_back(p.first);
    }
  }
}
