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>
struct Dsu {
  std::vector<int> ps;
  std::vector<int> ds;
  Dsu(size_t size) : ps(size), ds(size) {
    for (int i = 0; i < size; ++i) {
      ps[i] = i;
    }
  }
  int parent(int i) { return ps[i] == i ? i : ps[i] = parent(ps[i]); }
  bool same(int i, int j) { return parent(i) == parent(j); }
  void merge(int i, int j) {
    i = parent(i), j = parent(j);
    if (i == j) return;
    if (ds[i] < ds[j]) std::swap(i, j);
    ps[j] = i;
    if (ds[i] == ds[j]) ds[i] += 1;
  }
};
struct Graph {
  std::vector<std::map<int, int>> edges;
  Graph(size_t size) : edges(size) {}
  void connect(int i, int j) {
    edges[i][j] += 1;
    edges[j][i] += 1;
  }
  void disconnect(int i, int j) {
    edges[i][j] -= 1;
    edges[j][i] -= 1;
    if (edges[i][j] == 0) {
      edges[i].erase(j);
      edges[j].erase(i);
    }
  }
  struct Dfs {
    const Graph &graph;
    int from, to;
    std::set<int> used;
    Dfs(const Graph &graph, int from, int to)
        : graph(graph), from(from), to(to) {}
    operator bool() { return find(from); }
    bool find(int v) {
      if (v == to) {
        return true;
      }
      if (used.count(v) != 0) {
        return false;
      }
      used.insert(v);
      for (auto [u, _] : graph.edges[v])
        if (find(u)) return true;
      return false;
    }
  };
  bool connected(int i, int j) const { return Dfs(*this, i, j); }
};
struct BlockProceeder {
  Dsu dsu;
  Graph graph;
  bool connected(int i, int j) {
    auto u = dsu.parent(i), v = dsu.parent(j);
    return graph.connected(u, v);
  }
  std::set<std::pair<int, int>> odds;
  void inverse_edge(int i, int j) {
    if (i > j) std::swap(i, j);
    auto u = dsu.parent(i), v = dsu.parent(j);
    if (odds.count({i, j})) {
      graph.disconnect(u, v);
      odds.erase({i, j});
    } else {
      graph.connect(u, v);
      odds.insert({i, j});
    }
  }
};
struct Query {
  int type;
  int u, v;
  auto edge() const -> std::pair<int, int> { return {u, v}; }
  auto inc(int size) -> Query & {
    (++u) %= size;
    (++v) %= size;
    if (u > v) std::swap(u, v);
    return *this;
  }
};
std::istream &operator>>(std::istream &is, Query &query) {
  is >> query.type >> query.u >> query.v;
  --query.u, --query.v;
  if (query.u > query.v) {
    std::swap(query.u, query.v);
  }
  return is;
}
struct BlockCreator {
  const std::vector<Query> &queries;
  const size_t size;
  size_t begin, end;
  using Edges = std::set<std::pair<int, int>>;
  auto prefix_edges() const -> std::pair<Edges, Edges> {
    Edges stable;
    for (size_t i = 0; i < begin; ++i)
      if (queries[i].type == 1) {
        auto edge = queries[i].edge();
        if (stable.count(edge)) {
          stable.erase(edge);
        } else {
          stable.insert(edge);
        }
      }
    Edges unstable;
    for (size_t i = begin; i < end; ++i)
      if (queries[i].type == 1) {
        auto edge1 = queries[i].edge();
        auto edge2 = Query(queries[i]).inc(size).edge();
        if (stable.erase(edge1)) unstable.insert(edge1);
        if (stable.erase(edge2)) unstable.insert(edge2);
      }
    return {stable, unstable};
  }
  operator BlockProceeder() const {
    Dsu dsu(size);
    Graph graph(size);
    auto [stable, unstable] = prefix_edges();
    for (auto [u, v] : stable) dsu.merge(u, v);
    auto result = BlockProceeder{dsu, graph};
    for (auto [u, v] : unstable) result.inverse_edge(u, v);
    return result;
  }
};
struct Decomposer {
  const size_t size;
  std::vector<Query> &queries;
  std::vector<bool> answers;
  auto last() const -> bool { return answers.empty() ? false : answers.back(); }
  auto solve() -> std::vector<bool> {
    size_t block_size = queries.size() / 22.8 + 1488;
    for (size_t begin = 0, end = block_size;
         end = std::min(end, queries.size()), begin < queries.size();
         begin = end, end += block_size) {
      auto creator = BlockCreator{queries, size, begin, end};
      auto proceeder = static_cast<BlockProceeder>(creator);
      for (size_t i = begin; i < end; ++i) {
        auto &query = queries[i];
        if (last()) query.inc(size);
        auto [u, v] = query.edge();
        if (query.type == 1) {
          proceeder.inverse_edge(u, v);
        } else {
          auto answer = proceeder.connected(u, v);
          answers.push_back(answer);
        }
      }
    }
    return answers;
  }
};
auto main() -> int {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  size_t n, m;
  std::cin >> n >> m;
  auto queries = std::vector<Query>(m);
  for (Query &query : queries) {
    std::cin >> query;
  }
  std::vector<bool> answers = Decomposer{n, queries}.solve();
  for (bool answer : answers) {
    std::cout << answer;
  }
  std::cout << '\n';
  return 0;
}
