题目描述

qwqwq。

蓝龙亵渎打几点伤害？

qwq 在玩炉石传说的时候总是打不出教科书般的亵渎，于是他重新写了一个『炉石传说』，并且将亵渎的描述改为：「等概率随机在 $[L,R]$ 中选出一个整数作为伤害值 $d$，对所有随从造成 $d$ 点伤害，如果有随从死亡，则再次施放该法术，但伤害值不重新随机；如果没有随从死亡，则停止释放」，还去掉了场面上随从上限和亵渎最多触发 $14$ 次的限制。qwq 不知道这个改版亵渎的效果怎么样，于是他打算进行一些测试，其中共进行 $m$ 次如下类型的操作：

1. 在场面上加入一个血量为 $h$ 的随从，这里随从的血量都不能超过 $n$；

2. 给定 $[L,R]$，询问亵渎期望触发多少次；qwq 只会做操作 $1$，于是他就把操作 $2$ 交给你啦。

输入格式

第一行两个由空格分隔的整数 $n\ m$；接下来 $m$ 行，每行表示一次操作，操作 $1$ 表示为 $1\ h$，操作 $2$ 表示为 $2\ L\ R$；

输出格式

为避免输出小数，对每次操作 $2$，输出一个整数表示期望值与 $(R-L+1)$ 的乘积。

样例

10 10
2 7 9
1 6
2 7 10
1 10
1 7
2 7 10
1 7
1 1
2 6 7
1 4

3
8
11
6

数据范围与提示

对于其中 $19\%$ 的数据，$n,m\le 10^3$。

对于另外 $19\%$ 的数据，每次的 $2$ 操作满足 $L = R$。

对于另外 $19\%$ 的数据，所有 $2$ 操作都在 $1$ 操作后。

对于另外 $19\%$ 的数据，$m\le10^5$。

对于 $100\%$ 的数据，保证：$1\le n\le 10^5$，每次 $1$ 操作有 $1\le h\le n$，每次 $2$ 操作有 $1\le L\le R\le n, 1\le m\le 10^6$；以上所有数值均为整数。