题目背景

敌军即将发动突袭,指挥官紧急下令在一条防御战壕中布设地雷。战壕被划分为 $n$ 个位置,工兵每次可以在一段连续区间内布设一种新型地雷。指挥官需要随时了解某段区间内共有多少种不同的地雷,以便调整防御策略。

题目描述

防御战壕是一条长度为 $n$ 的直线,工兵每次可以在 $[L, R]$ 区间布设一种之前未使用过的地雷。由于战况紧急,指挥官可能会随时询问在 $[L',R']$ 区间内有多少种不同的地雷,他希望你能尽快给出答复。

输入格式

第一行为两个整数 $n$ 和 $m$,$n$ 表示战壕长度,$m$ 表示布雷次数及询问次数之和。

接下来有 $m$ 行,每行三个整数 $q,l,r$:

• 若 $q=1$,则表示在 $[l, r]$ 区间布设一种新地雷;
• 若 $q=2$,则表示询问当前 $[l, r]$ 区间共有多少种地雷。

输出格式

对于每次询问,输出一个答案（单独一行）,表示当前区间内的地雷种数。

样例

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

1
2

提示

对于 $30\%$ 的数据,$0 \le n$, $m \le 1000$。

对于 $100\%$ 的数据,$0 \le n$, $m \le 10^5$。