問題文

$N$ 頂点 $0$ 辺の無向グラフがあります。頂点にはそれぞれ $1$ から $N$ までの番号が付けられています。
以下のような $Q$ 個のクエリが与えられるので順に処理してください。

• 1 L R：$L \leq u < v \leq R$ を満たす頂点対 $(u, v)$ についてすべて辺で結ぶ。
• 2 L R：$1 \leq u < R$ 、$L < v \leq N$ を満たす頂点対 $(u, v)$ を端点とする辺をすべて削除する。
• 3 u v：頂点 $u$ と頂点 $v$ が連結であるかを判定する。連結であれば1、連結でなければ0を出力する。
• 4 v：頂点 $v$ が属する連結成分に含まれる頂点の個数を出力する。

入力

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

• ${\rm Query}_{i}$について
  タイプ1またはタイプ2のクエリのとき

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

  タイプ3のクエリのとき

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

  タイプ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$
• 入力はすべて整数

出力

タイプ3、タイプ4のクエリが合計で $K$ 個与えられるとして、 $i\ (1 \leq i \leq K)$ 行目にそれぞれのクエリの回答を1行に出力してください。

サンプル

サンプル1

入力

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

出力

1
2
1
0
1
5
10
2
1
5

サンプル1の説明を見る (クリックで展開します)

タイプ1、タイプ2のクエリに相当する区間は以下のようになっています。(黒：タイプ1、赤：タイプ2)

• 4 3：頂点 $3$ と連結である頂点は1つなので 1 を出力します。
• 1 1 2：頂点対 $(1, 2)$ について辺で結びます。
• 4 1：頂点 $1$ と連結である頂点は2つなので 2 を出力します。(頂点 $1$ , $2$)
• 1 2 3：頂点対 $(2, 3)$ について辺で結びます。
• 3 1 3： 頂点 $1$ と頂点 $3$ は連結なため 1 を出力します。
• 1 6 7：頂点対 $(6, 7)$ について辺で結びます。
• 1 8 9：頂点対 $(8, 9)$ について辺で結びます。
• 3 7 8： 頂点 $7$ と頂点 $8$ は連結ではないなため 0 を出力します。
• 1 7 10：頂点対 $(7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)$ について辺で結びます。
• 3 6 10：頂点 $6$ と頂点 $10$ は連結なため 1 を出力します。
• 1 7 9：頂点対 $(7, 8), (7, 9), (8, 9)$ について辺で結びます。
• 4 10：頂点 $10$ と連結である頂点は5つなので 5 を出力します。(頂点 $6, 7, 8, 9, 10$)
• 1 2 8：以下の頂点対について辺で結びます。
  $(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：頂点 $5$ と連結である頂点は10個なので 10 を出力します。(頂点 $1$ ～ $10$)
• 2 2 6：以下の頂点対について存在する辺を削除します。($(u, v) = (v, u)$ の重複や同一頂点を省いています。)
  $(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：頂点 $2$ と連結である頂点は2つなので 2 を出力します。(頂点 $1$ , $2$)
• 4 5：頂点 $5$ と連結である頂点は1つなので 1 を出力します。
• 4 6：頂点 $6$ と連結である頂点は5つなので 5 を出力します。(頂点 $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