EIはBJOIの直前合宿で集合のブロック分割に関する問題を聞いたが、彼は非常に弱く（今もなお弱い）、他人のアルゴリズムより $\log$ が一つ多くなってしまう。彼が思いついた解決策は、ブロックサイズを調整することで計算量を $\Theta(n \sqrt{n\log n})$ に抑えることだけだった。しかし、修正された問題を見ると、彼はまた解けなくなってしまった。

$n$ 個の集合 $S_i$ があり、初期状態はすべて空である。次に $q$ 回の操作を行う。

1. 第 $l$ 番目の集合から第 $r$ 番目の集合に要素 $x$ を挿入する。すなわち、$l \le i \le r$ に対して $S_i \leftarrow S_i \cup \{x\}$ とする。
2. 第 $l$ 番目の集合から第 $r$ 番目の集合の共通部分のサイズを求める。すなわち、$$\left| \bigcap_{i = l}^r S_i \right|$$ を求める。

入力

一行目に整数 $n, q$ が与えられる。

続く $q$ 行には、各操作が与えられる。各行の最初の数値 $op$ は操作の種類を表す。

操作の種類に応じた入力形式は、1 $l\ r\ x$ または 2 $l\ r$ である。

出力

操作 2（クエリ）ごとに、答えを整数で一行に出力せよ。

入出力例

入力 1

3 4
1 1 2 2
1 2 3 1
2 1 2
2 2 2

出力 1

1
2

注記 1

操作後の各集合は $[\{2\},\{1,2\},\{1\}]$ となる。

したがって、最初のクエリについては $\{2\} \cap \{1, 2\} = \{2\}$ となる。

入力 2

2 3
1 1 1 1
1 2 2 1
2 1 2

出力 2

1

制約

$1\le n, q \le 3 \times 10^5$, $1\le x \le q$, $1 \le l \le r \le n$

Subtask 1 (12 pts.)，$1\le n, q \le 500$，挿入される要素の総数 $|S| \le 10^5$

Subtask 2 (18 pts.)，$1 \le n, q \le 5 \times 10^3$，挿入される要素の総数 $|S| \le 10^5$

Subtask 3 (20 pts.)，$1\le n, q \le 10^5$，挿入される要素の総数 $|S| \le 10^5$

Subtask 4 (28 pts.)，$1\le n, q \le 10^5$

Subtask 5 (22 pts.)，$1 \le n, q \le 3 \times 10^5$

Subtask $+\infty$ (0 pts.)，この区間のすべての部分区間に対する答えの総和を求める必要がある。