Problem Description

Takahashi is the owner of a factory. Currently, it is on vacation and the factory has no products. However, starting from the first day after the vacation, the factory is scheduled to produce K products every day.

Additionally, this factory is very popular and sometimes receives orders. However, the orders received by this factory are a bit unusual and are made in the following format:

• Order (D, A): After the production of products is completed up to the D-th day after the vacation, up to A products can be purchased. The actual number of products sold can be chosen by Takahashi within the range of 0 to A. However, it is not possible to sell more products than the inventory allows.

As the programming responsible for this factory, you will be given Q pieces of information from Takahashi regarding order additions or accounting inquiries. The i-th piece of information is input in the following format:

• Order addition "1 Di Ai": An order in the format (Di, Ai) is added to the factory.
• Accounting inquiry "2 Di": Determine the maximum number of products that can be sold after the production and processing of orders up to the Di-th day after the vacation, considering only the orders received up to the time of the inquiry.

Please accurately answer all accounting inquiries to assist Takahashi in managing his business.

Input Format

The input is given from the standard input in the following format:

Q K Information_1 Information_2 : Information_Q

Output Format

Output the answers to the accounting inquiries in the order they are given, each on a separate line.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
2
6

Sample Input #2

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

Sample Output #2

5
9

Sample Input #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

Sample Output #3

0
7
0
0
7
14
0

Notes/Hints

Constraints

• $ 1 ≦ Q ≦ 10^5 $
• $ 1 ≦ K ≦ 10^9 $
• $ 1 ≦ Di ≦ 10^9 $
• $ 1 ≦ Ai ≦ 10^9 $

Partial Points

• For 600 points worth of test cases, the value of Di in accounting inquiries is always $ 10^9 $.

Sample Explanation 1

For example, the optimal way to sell products for the last accounting inquiry is as follows:
- On the first day after the vacation, produce 2 products and then sell 1 product. At this point, 1 product remains.
- On the second day after the vacation, produce 2 products. At this point, 3 products remain.
- On the third day after the vacation, produce 2 products and then sell 5 products.

Sample Explanation 2

This input satisfies the partial points constraints.

见题面 Input 部分

见题面 Output 部分