Welcome to ZOJ
74 - ZOJ Monthly, January 2009 - E

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:

  1. a1<=A<=a2;
  2. 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.


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. 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. 2 A B: lottery draw.
1 <= a1 <= a2 <= 10000; 1 <= b <= 1e9; 1 <= A <= 10000; 1 <= B <= 1e9; All numbers are integers.


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

AAB 1470
AAC 735

Author: JIANG, Guangran
Source: ZOJ Monthly, January 2009
Submit    Status