Lottery

Time Limit: 10 Seconds
Memory Limit: 131072 KB

There is a kind of lottery. Each ticket has three numbers *a1*, *a2*,
*b* with the price of *(a2-a1+1)* yuan. When someone buy the lottery,
the money will be put into the prize pool and the ticket will be put into tickets
list. Two numbers *A*, *B* will be given when the lottery was drawed.
All tickets in list satisfying following two conditions are winning tickets:

*a1*<=*A*<=*a2*;
*b* is closest to *B*.

Note that there may be more than one winning tickets.

All winning tickets share all the money in the prize pool. But each ticket can only
get integer yuan, so the rest of the money will be left in the pool. All winning
tickets will be removed from list, even if the money it get is 0 yuan.

**Input**

For each case, the first line contains 2 integers 1 <= *n* <= 200000 and
0 <= *m* <= 1e6 where *m* is the initial money in pool and the initial
list is empty. Then following *n* lines, each line is an action. Actions are in
two forms:

- 1
*strname* *a1* *a2* *b*: someone called *strname*
buy a ticket with the numbers *a1*, *a2*, *b* and *strname*
contains no more than 7 characters.
- 2
*A* *B*: lottery draw.

1 <= a1 <= a2 <= 10000; 1 <= b <= 1e9; 1 <= A <= 10000;
1 <= B <= 1e9; All numbers are integers.

**Ouput**

For each lottery draw, first ouput one line contains an integer *k*, the number
of winners. Then following *k* lines, each line contains one winner's name and
the money of his prize, separated with one space. Output winners in their name's
lexicographic order.

**Sample Input**

7 1111
1 AAB 1 999 777
2 1000 222
1 AAB 10 100 776
1 AAB 876 879 775
1 AAC 878 878 775
2 878 776
2 99 1

**Sample Output**

0
2
AAB 1470
AAC 735
1
AAB 1

Author:

**JIANG, Guangran**
Source:

**ZOJ Monthly, January 2009**
Submit
Status