[Ynoi2015] 我回来了

题目背景

我遵守了... 约...约定 ![](https://cdn.luogu.com.cn/upload/pic/45543.png) 【你非常努力啊】 我非常非常努力哦... ![](https://cdn.luogu.com.cn/upload/pic/45545.png) 【虽然昨天也说过这句话了...】 【欢迎回来,珂朵莉】 ![](https://cdn.luogu.com.cn/upload/pic/45546.png) 我回来了... 终于说出口了... 【是啊,我终于听见了】 红色的头发,会不会奇怪? 【很漂亮的颜色,和你很搭哦】 是吗... 我...我已经没事了 【真的吗?身体状况没问题吗?】 【要是硬撑的话,我可不会饶过你啊】 没事的,做饭啊洗衣服啊,还留着很多活要干呢 【可别太拼了哦】 ![](https://cdn.luogu.com.cn/upload/pic/45547.png) 哼,你就做好心理准备等着吧 ![](https://cdn.luogu.com.cn/upload/pic/45548.png)

题目描述

珂朵莉在玩炉石传说的时候总是打不出教科书般的亵渎,于是他重新写了一个炉石传说’,并且将亵渎的描述改为:“等概率随机在 $[L,R]$ 中选出一个整数作为伤害值 $d$,对所有随从造成 $d$ 点伤害,如果有随从死亡,则再次施放该法术,但伤害值不重新随机;如果没有随从死亡,则停止释放”,还去掉了场面上随从上限和亵渎最多触发14次的限制。 珂朵莉不知道这个改版亵渎的效果怎么样,于是他打算进行一些测试,其中共进行 $m$ 次如下类型的操作: 1. 在场面上加入一个血量为 $h$ 的随从,这里随从的血量都不能超过 $n$; 2. 给定 $L, R$,询问亵渎期望触发多少次; 珂朵莉只会做操作1,于是他就把操作2交给你啦。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #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

输出样例 #1

3
8
11
6

说明

Idea:oscar,Solution:ccz181078,Code:ccz181078,Data:nzhtl1477 对于 $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$; 以上所有数值均为整数。