問題文

高橋君は工場の経営者です。 今は休暇中であり工場には商品が $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$ である。

入力例 1Copy

5 2
1 3 5
2 1
1 1 3
2 1
2 3

出力例 1Copy

0
2
6

例えば、最後の経理質問のときの最適な商品の売り方は以下のようになります。

• 休暇明け $1$ 日目に商品を $2$ 個生産して、その後商品を $1$ 個売る。このとき、商品は $1$ 個残る。
• 休暇明け $2$ 日目に商品を $2$ 個生産する。このとき、商品は $3$ 個残る。
• 休暇明け $3$ 日目に商品を $2$ 個生産して、その後商品を $5$ 個売る。

入力例 2Copy

4 2
1 5 5
2 1000000000
1 2 7
2 1000000000

出力例 2Copy

5
9

この入力は部分点の制約を満たします。

入力例 3Copy

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

出力例 3Copy

0
7
0
0
7
14
0