#6723. 「CodePlus #7」教科书般的亵渎

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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 ;以上所有数值均为整数。