#1011. 小田的存钱罐

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

题目描述

南国因为常年政治斗争,领导位置换的十分频繁,每次领导上位都会重新推出一套不同面值的货币。

一开始大家都不适应,后来因为货币种类实在太多,从 的面值全部齐全了,大家也就无所谓了。

小田是南国一名会画画的平凡高三生,她在生日中收到了一个小猪存钱罐,于是决定用这个存钱罐来存接稿过程中赚取的钞票。 小田可能会对存钱罐有两种操作:

操作1:将一张面值为 的钞票加入存钱罐中。

操作2:从存钱罐中取出 张面值为 的钞票,如果面值为 的钞票不足 则取出所有面值为 的钞票。

在这个过程中小田时不时会问你存钱罐中面值最大的钞票减去面值最小的钞票的值,保证此时存钱罐里有钱。

输入格式

第一行一个整数 ,表示小田操作次数和询问次数的总和。

接下来 行,每行第一个数 表示:

时,接下来一个数字 表示要放入钞票的面值。

时,接下来两个数字 分别表示要取出钞票的面值和张数。

时,小田向你发出询问。

输出格式

一行一个整数,表示检测区间的个数。

样例

样例输入1:

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

样例输出1:

1
5
4

样例输入2:

4
1 10000
1 1000
2 100 3
1 10

样例输出2:


数据范围与提示

样例解释 1

存钱罐S的转换如下:

  • 第一次查询:将 存入 中。此时
  • 第二次查询:将 存入 中。此时
  • 第三次查询: 的最大值为 ,最小值为 ,所以输出
  • 第四次查询:将 存入 中。此时
  • 第五次查询:将 存入 中。此时
  • 第六次查询: 的最大值为 ,最小值为 ,所以输出
  • 第七次查询:由于 中有两个 ,并且 ,因此从 中取出两次 。此时
  • 第八次查询: 的最大值为 ,最小值为 ,所以输出

样例解释 2

如果给定的查询中不包含类型为3的查询,则不应输出任何内容。

数据范围

对于所有的数据,满足:

  • 保证输入数值为整数