1217_F. Forced Online Queries Problem_33359
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 
import java.io.*;
import java.util.*;

public class CF1217F extends PrintWriter {
	CF1217F() { super(System.out, true); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1217F o = new CF1217F(); o.main(); o.flush();
	}

	int[] dsu;
	int find(int i) {
		return dsu[i] < 0 ? i : (dsu[i] = find(dsu[i]));
	}
	void join(int i, int j) {
		i = find(i);
		j = find(j);
		if (i == j)
			return;
		if (dsu[i] > dsu[j])
			dsu[i] = j;
		else {
			if (dsu[i] == dsu[j])
				dsu[i]--;
			dsu[j] = i;
		}
	}

	static final int K = 400;
	int[] next, zz, jj; int l_ = 1;
	int link(int l, int z, int j) {
		next[l_] = l; zz[l_] = z; jj[l_] = j;
		return l_++;
	}
	byte[] used;
	int[] ao, visited;
	void init(int n, int m) {
		next = new int[1 + m * 2];
		zz = new int[1 + m * 2];
		jj = new int[1 + m * 2];
		ao = new int[n];
		visited = new int[n]; Arrays.fill(visited, -1);
	}
	int dfs(int i, int t, int h) {
		if (i == t)
			return 1;
		if (visited[i] == h)
			return 0;
		visited[i] = h;
		for (int l = ao[i]; l != 0; l = next[l])
			if (used[zz[l]] == 1 && dfs(jj[l], t, h) == 1)
				return 1;
		return 0;
	}
	void main() {
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] tt = new int[m];
		int[] xx = new int[m * 2];
		int[] yy = new int[m * 2];
		int[] xx_ = new int[m * 2];
		int[] yy_ = new int[m * 2];
		int[] hh = new int[m * 2];
		for (int h = 0; h < m; h++) {
			tt[h] = sc.nextInt();
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			if (x > y) {
				int tmp = x; x = y; y = tmp;
			}
			xx[h << 1] = x;
			yy[h << 1] = y;
			x = (x + 1) % n;
			y = (y + 1) % n;
			if (x > y) {
				int tmp = x; x = y; y = tmp;
			}
			xx[h << 1 | 1] = x;
			yy[h << 1 | 1] = y;
		}
		Integer[] ii = new Integer[m * 2];
		for (int h = 0; h < m * 2; h++)
			ii[h] = h;
		Arrays.sort(ii, (i, j) -> xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j]);
		int m_ = 0;
		for (int h = 0; h < m * 2; h++) {
			xx_[m_] = xx[ii[h]];
			yy_[m_] = yy[ii[h]];
			hh[ii[h]] = h + 1 == m * 2 || xx[ii[h + 1]] != xx[ii[h]] || yy[ii[h + 1]] != yy[ii[h]] ? m_++ : m_;
		}
		used = new byte[m_];	// indexed by hh
		// 0: not used
		// 1: used and not deleted in this round
		// 2: not used but maybe used in this round
		// 3: used but maybe deleted in this round
		dsu = new int[n];
		init(n, m_);
		byte[] ans = new byte[m];
		int last = 0, cnt = 0;
		for (int l = 0; l < m; l += K) {
			int r = Math.min(l + K, m);
			for (int h = l; h < r; h++)
				if (tt[h] == 1)
					for (int p = 0; p <= 1; p++) {
						int h_ = hh[h << 1 | p];
						used[h_] |= 2;
					}
			Arrays.fill(dsu, -1);
			for (int h_ = 0; h_ < m_; h_++)
				if (used[h_] == 1)
					join(xx_[h_], yy_[h_]);
			l_ = 1; Arrays.fill(ao, 0);
			for (int h = l; h < r; h++)
				if (tt[h] == 1)
					for (int p = 0; p <= 1; p++) {
						int h_ = hh[h << 1 | p];
						int x = find(xx_[h_]), y = find(yy_[h_]);
						if (used[h_] < 2)
							continue;
						used[h_] ^= 2;
						ao[x] = link(ao[x], h_, y);
						ao[y] = link(ao[y], h_, x);
					}
			for (int h = l; h < r; h++) {
				int h_ = hh[h << 1 | last];
				int x = find(xx_[h_]), y = find(yy_[h_]);
				if (tt[h] == 1)
					used[h_] ^= 1;
				else {
					last = dfs(x, y, h);
					ans[cnt++] = (byte) (last + '0');
				}
			}
		}
		println(new String(ans, 0, cnt));
	}
}
