74 - ZOJ Monthly, January 2009 - E
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:
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:
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.
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
0 2 AAB 1470 AAC 735 1 AAB 1
Author: JIANG, Guangran
Source: ZOJ Monthly, January 2009