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 int MAXN = 200005;
const int B = 500;
template <int MAXN>
struct dsu_t {
  int fa[MAXN + 1];
  void clear() { memset(fa, 0, sizeof fa); }
  int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
  void link(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) fa[u] = v;
  }
  bool linked(int u, int v) { return find(u) == find(v); }
};
template <int MAXN, int MAXM, typename T = int>
struct vlist_t {
  struct node {
    int from;
    T to;
    int next;
  } edge[MAXM + 1];
  int head[MAXN + 1], top;
  vlist_t() { top = 0; }
  void clear() {
    for (int i = 1; i <= top; i++) head[edge[i].from] = 0;
    top = 0;
  }
  void push(int i, const T &j) {
    edge[++top] = (node){i, j, head[i]}, head[i] = top;
  }
  T &get(int id) { return edge[id].to; }
  int next(int id) { return edge[id].next; }
  int first(int id) { return head[id]; }
};
template <int MAXN>
struct graph_t {
  vlist_t<MAXN, MAXN> vlist;
  int vis[MAXN + 1], dfstime;
  void clear() { vlist.clear(); }
  void push(int x, int y) {
    vlist.push(x, y);
    vlist.push(y, x);
  }
  bool dfs_link(int nd, int tar) {
    if (tar == nd) return true;
    vis[nd] = dfstime;
    bool ans = false;
    for (int i = vlist.first(nd); i; i = vlist.next(i)) {
      int to = vlist.get(i);
      if (vis[to] != dfstime) ans = ans || dfs_link(to, tar);
    }
    return ans;
  }
  bool linked(int x, int y) {
    ++dfstime;
    return dfs_link(x, y);
  }
};
namespace workspace {
int n, m;
int tp[MAXN], u[MAXN], v[MAXN], ans[MAXN];
int ans_batch[MAXN];
int last_ans;
struct my_pair {
  int first;
  int second;
  my_pair() { first = second = 0; }
  my_pair(int u, int v) {
    if (u > v) swap(u, v);
    first = u, second = v;
  }
  friend bool operator<(const my_pair &a, const my_pair &b) {
    return a.first == b.first ? a.second < b.second : a.first < b.first;
  }
};
set<my_pair> edges;
void input() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &tp[i], &u[i], &v[i]);
  last_ans = 0;
}
void output() {
  for (int i = 1; i <= m; i++)
    if (tp[i] == 2) printf("%d", ans[i]);
  puts("");
}
int local_tp[B], local_u[B], local_v[B];
int local_top;
dsu_t<MAXN> dsu;
set<my_pair> candidate_edges;
void init_block() {
  local_top = 0;
  candidate_edges.clear();
}
void add_query(int tp, int u, int v) {
  local_tp[local_top] = tp;
  local_u[local_top] = u;
  local_v[local_top] = v;
  local_top++;
}
void build_block() {
  dsu.clear();
  int ce_top = 0;
  static my_pair c_edge[2 * B];
  for (int j = 0; j < local_top; j++) {
    if (local_tp[j] != 1) continue;
    auto p = make_pair(local_u[j], local_v[j]);
    int x = p.first, y = p.second;
    auto nxt_pt = [](int x) { return x == n ? 1 : x + 1; };
    auto select = [&](const my_pair &p) {
      if (edges.count(p)) {
        c_edge[ce_top++] = p;
        edges.erase(p);
      }
    };
    select({x, y});
    select({nxt_pt(x), nxt_pt(y)});
  }
  for (auto p : edges) {
    dsu.link(p.first, p.second);
  }
  for (int j = 0; j < ce_top; j++) {
    auto &p = c_edge[j];
    candidate_edges.insert(p);
  }
}
int get_ans(int u, int v) {
  u = dsu.find(u);
  v = dsu.find(v);
  static graph_t<MAXN> graph;
  graph.clear();
  for (auto p : candidate_edges) {
    int x = p.first, y = p.second;
    graph.push(dsu.find(x), dsu.find(y));
  }
  return graph.linked(u, v);
}
void calc_block() {
  auto select = [](int x, int y) {
    if (candidate_edges.count({x, y}))
      candidate_edges.erase({x, y});
    else
      candidate_edges.insert({x, y});
  };
  for (int j = 0; j < local_top; j++) {
    int u = local_u[j];
    int v = local_v[j];
    local_u[j] = u = (u + last_ans - 1) % n + 1;
    local_v[j] = v = (v + last_ans - 1) % n + 1;
    if (local_tp[j] == 1) {
      select(u, v);
    } else {
      last_ans = ans_batch[j] = get_ans(u, v);
    }
  }
  for (auto p : candidate_edges) edges.insert(p);
}
void work() {
  for (int i = 1; i <= m; i += B) {
    init_block();
    for (int j = 0; j < B && i + j <= m; j++) {
      add_query(tp[i + j], u[i + j], v[i + j]);
    }
    build_block();
    calc_block();
    for (int j = 0; j < B && i + j <= m; j++) {
      ans[i + j] = ans_batch[j];
    }
  }
}
}  // namespace workspace
int main() {
  workspace::input();
  workspace::work();
  workspace::output();
  return 0;
}
