配点 : 1000 点
問題文
高桥君是工厂的经营者。 现在正在休假,工厂里没有商品, 1 休假结束后, 1 第几天起每天计划生产 K 个商品。
此外,这家工厂非常受欢迎,有时会接到订单。 但是,这家工厂接到的订单稍微有些特殊,采用以下形式进行。
- 注文 (D,A) : 从休假结束后的 D 第几天起,商品生产完成后,最多可以 A 个被购买。实际卖出的数量可以由高桥君在 0~A 个范围内选择。但是,不能超过库存数量。
作为这家工厂的编程负责人,你会收到高桥君关于新增订单或财务问题的 Q 信息。 i 第几条信息将以以下形式输入。
- 注文追加「1\ D_i\ A_i」: (D_i,A_i) 这种形式的订单会被添加到工厂。
- 経理質問「2\ D_i」: 到提问时为止收到的订单为准,休假结束后的 D_i 天内完成商品生产和订单处理时,最多可以销售多少商品。
请正确回答所有财务问题,帮助高桥君管理经营。
制約
- 1 ≦ Q ≦ 10^5
- 1 ≦ K ≦ 10^9
- 1 ≦ D_i≦ 10^9
- 1 ≦ A_i≦ 10^9
部分点
- 600 在小部分测试用例中,财务问题中的 D_i 值总是 10^9 。
入力
输入是按以下格式从标准输入给出的。
Q K Information_1 Information_2 : Information_Q
出力
财务问题的答案,按问题给出的顺序分别 1 逐行输出。
入力例 1
5 2 1 3 5 2 1 1 1 3 2 1 2 3
出力例 1
0 2 6
例如,在最后一个财务问题时的最佳商品销售方式如下。
- 休假结束后的 1 天生产商品 2 个,然后销售商品 1 个。这时,商品剩余 1 个。
- 休假结束后的 2 天生产商品 2 个生产。这时,商品是 3 个。
- 休假结束后的 3 天生产商品 2 个,然后销售商品 5 个卖出。
入力例 2
4 2 1 5 5 2 1000000000 1 2 7 2 1000000000
出力例 2
5 9
此输入满足部分得分的限制。
入力例 3
10 4 2 6 1 5 7 2 6 2 4 2 1 2 7 1 5 7 2 7 2 2 1 4 6
出力例 3
0 7 0 0 7 14 0