题目描述

原题来自：[Vijos P1448] 校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：

• $\red{K=1}$，读入$\red{ l,r}$ 表示在 $\red{l}$ 到 $\red{r }$之间种上一种树，每次操作种的树的种类都不同；
• $\red{K=2}$，读入$\red{ l,r }$表示询问 $\red{l }$到 $\red{r }$之间有多少种树。

注意：每个位置都可以重复种树。

输入格式

第一行$\red{ n,m }$表示道路总长为 $\red{n}$，共有$\red{ m}$ 个操作； 接下来$\red{ m }$行为 $\red{m }$个操作。

输出格式

对于每个 $\red{k=2}$ 输出一个答案。

样例

输入样例

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

输出样例

1
2

提示

对于 $\red{20\% }$的数据，$\red{1\le n,m\le 100}$； 对于 $\red{60\% }$的数据，$\red{1\le n\le 10^3,1\le m\le 5\times 10^4}$； 对于$\red{ 100\%}$ 的数据，$\red{1\le n,m\le 5\times 10^4}$，保证 $\red{l,r\gt 0}$。