Problem Statement

There is an undirected graph with $N$ vertices and $0$ edges. The vertices are numbered from $1$ to $N$.
You are given $Q$ queries of the following kinds. Process them in order.

• 1 L R: For every vertex pair $(u, v)$ satisfying $L \leq u < v \leq R$, connect the pair with an edge.
• 2 L R: Delete all edges whose endpoints are a vertex pair $(u, v)$ satisfying $1 \leq u < R$ and $L < v \leq N$.
• 3 u v: Determine whether vertex $u$ and vertex $v$ are connected. Output 1 if they are connected, and 0 if they are not.
• 4 v: Output the number of vertices in the connected component containing vertex $v$.

Input

$N\ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

• For ${\rm Query}_{i}$:
  For a query of type 1 or type 2

  ${\rm type}_{i}\ L_{i}\ R_{i}$

  For a query of type 3

  ${\rm type}_{i}\ u_{i}\ v_{i}$

  For a query of type 4

  ${\rm type}_{i}\ v_{i}$

• $2 \leq N \leq 10^{9}$
• $1 \leq Q \leq 2 \times 10^{5}$
• $1 \leq {\rm type}_{i} \leq 4$
• $1 \leq L_{i} < R_{i}\leq N$
• $1 \leq u_{i}, v_{i}\leq N$
• All input values are integers.

Output

Let $K$ be the total number of queries of type 3 and type 4. On line $i\ (1 \leq i \leq K)$, output the answer to the corresponding query, one per line.

Sample

Sample 1

Input

10 18
4 3
1 1 2
4 1
1 2 3
3 1 3
1 6 7
1 8 9
3 7 8
1 7 10
3 6 10
1 7 9
4 10
1 2 8
4 5
2 2 6
4 2
4 5
4 6

Output

1
2
1
0
1
5
10
2
1
5

View the explanation of Sample 1 (click to expand)

The intervals corresponding to the type 1 and type 2 queries are as follows. (Black: type 1, Red: type 2)

• 4 3: There is 1 vertex connected to vertex $3$, so output 1.
• 1 1 2: Connect the vertex pair $(1, 2)$ with an edge.
• 4 1: There are 2 vertices connected to vertex $1$, so output 2. (Vertices $1$ , $2$)
• 1 2 3: Connect the vertex pair $(2, 3)$ with an edge.
• 3 1 3: Vertex $1$ and vertex $3$ are connected, so output 1.
• 1 6 7: Connect the vertex pair $(6, 7)$ with an edge.
• 1 8 9: Connect the vertex pair $(8, 9)$ with an edge.
• 3 7 8: Vertex $7$ and vertex $8$ are not connected, so output 0.
• 1 7 10: Connect the vertex pairs $(7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)$ with edges.
• 3 6 10: Vertex $6$ and vertex $10$ are connected, so output 1.
• 1 7 9: Connect the vertex pairs $(7, 8), (7, 9), (8, 9)$ with edges.
• 4 10: There are 5 vertices connected to vertex $10$, so output 5. (Vertices $6, 7, 8, 9, 10$)
• 1 2 8: Connect the following vertex pairs with edges.
  $(2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8)$
  $(3, 4), (3, 5), (3, 6), (3, 7), (3, 8)$
  $(4, 5), (4, 6), (4, 7), (4, 8)$
  $(5, 6), (5, 7), (5, 8)$
  $(6, 7), (6, 8)$
  $(7, 8)$
• 4 5: There are 10 vertices connected to vertex $5$, so output 10. (Vertices $1$ to $10$)
• 2 2 6: Delete the existing edges for the following vertex pairs. (Duplicates of the form $(u, v) = (v, u)$ and pairs of identical vertices are omitted.)
  $(1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10)$
  $(2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10)$
  $(3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10)$
  $(4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10)$
  $(5, 6), (5, 7), (5, 8), (5, 9), (5, 10)$
  
• 4 2: There are 2 vertices connected to vertex $2$, so output 2. (Vertices $1$ , $2$)
• 4 5: There is 1 vertex connected to vertex $5$, so output 1.
• 4 6: There are 5 vertices connected to vertex $6$, so output 5. (Vertices $6, 7, 8, 9, 10$)

10 11
1 1 3
1 4 6
1 7 10
4 5
1 2 8
4 5
2 4 5
4 4
4 5
3 10 7
3 10 4

3
10
4
6
1
0

998244353 7
1 3 998244353
4 998244353
2 2 50
4 998244353
2 2023 20232023
4 2000
4 998244353

998244351
998244304
1974
978012331

2 9
3 1 1
3 2 2
1 1 2
3 1 1
3 2 2
3 1 2
2 1 2
3 1 1
3 2 2

1
1
1
1
1
1
1