You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

前情提要

在过去的半年中，kuro使用这种分组方法打出了很好的分数，不幸的是，面对一些抽象的谱面(与题目无关，请不要在赛时访问)，kuro需要新的分组方法！

具体的说，一共有$n$个音符，一共有四种操作。

$1 \space l \space r$，kuro认为从$l$到$r$的所有音符应该属于同一组。

$2 \space l \space r$，kuro认为$l$和$r$应该属于同一组。

$3 \space l \space r$，kuro想知道$l,r$是否属于同一组

$4 \space l \space r$，kuro反悔了，认为$[l,r]$的所有点都不应该和任何其他点属于同一组（即各自为一组）

两个音符$a$，$b$当且仅当符合以下三种情况时属于同一组(具体例子请阅读样例和样例解释)

1.$a,b$在kuro的某一次认定中被认为属于同一组音符

2.$a,c$因为第一种或此前因该种情况被认为属于同一组音符，$b，c$也因为第一种或此前因该种情况被认为属于同一组音符

3.第四种操作并不会影响以某个为中继点的点属于同一组，只是将[l,r]范围内的所有点都各自独立

Input Format

每个测试点的第一行为一个整数$T(1 \leq T \leq 100)$，表示该测试点有$T$组测试数据

每组测试数据的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^9$, $1 \leq q \leq 2*10^5$），分别表示音符的总数和操作数量。

接下来的 $q$ 行，每行有三个整数，第一个整数$op ( 1 \leq op \leq 4)$表示操作种类，接下来的 $2$ 个整数$l,r(1 \leq l \leq r \leq n)$,l,r与题目描述中含义相同

保证每个测试点的所有$q$的总和不超过$2*10^5$。

Output Format

对于第三个操作，若$l,r$属于同一组，你需要输出一行，只包含一个整数1，否则，你需要输出一行，只包含一个整数0

对于其他操作，你不需要输出。

Sample

输入 #1

1

5 5

1 1 3

2 3 5

2 1 3

4 2 4

3 1 5

输出 #1

1

样例解释

第一次操作后，分组为[1,2,3],[4],[5]

第二次操作后，分组为[1,2,3,5],[4]

第三次操作后，分组不变

第四次操作后，分组为[1,5],[2],[3],[4]

第五次操作为询问，分组不变

输入 #2

2

1000000000 3

1 1 3

1 4 5

3 3 4

10000000 3

1 1 1

3 2 2

1 1000 10000000

输出 #2

0
1