HUST Monthly 2010.04.05

From: 2010-04-05 12:00:00 To: 2010-04-05 17:00:00 Now: 2017-09-20 00:58:37 Status: Public

G - The XLPT Registration System

Time Limit: 1s Memory Limit: 128MB

Submissions: 286 Solved: 15
Description

One day, INFINITE_Li decided to attend the XLPT exam. Then he visited the XLPT registration website and register his information. He found the registration system for XLPT is very interesting, and decided to write a program to simulate the system. But, it is well known that he is poor at programming. So he turns to you and asks for your help. There are 3 steps to register for XLPT exam: 1. register your personal information on the website. 2. choose a test center to take the exam. 3. pay for the exam. All the test centers has a capacity K, which means the amount of the students that chosen this center must not excceed K at the same time. in more details, there are 4 kinds of request for the system: REG student_name GET student_name test_center_name PAY student_name CAL student_name REG is the request for step 1 above, GET is for step 2, and PAY is for step 3. The CAL request means the student want to rechoose a test center to take the exam, the system should will delete his name from his current chosen test center's namelist. What's more, if you had chosen your test center and didn't pay for the exam for T seconds, the system will delete your name from the namelist of the test center automatically. There are 4 more rules below: 1. the REG request is always the first request of an student, and one student will register only once. 2. IF A PERSON'S NAME IS ALREADY IN A TEST CENTER'S NAMELIST, HE CAN'T CHOOSE ANOTHER TEST CENTER. 3. if a person chose a test center and paid for the exam, then he couldn't cancel that anyway. 4. before you pay, your name must be in a test center's namelist All illegal requests will be ignored. now given all the requests, you are to determine where the paid student will take the exam.

Input

There are less than 10 test cases. For each test case there are 3 integers in the first line: N K T (N <= 50000). Then N lines, each line contains an request in the follow form: TIME REQ student_name [test_center_name] TIME is the time that the request will be processed by the system, and it is guaranteed it will be ascending in the input. note that only GET request contains "test_center_name" the length of student_name and test_center_name will not excceed 20, and no spaces will appear in a name.

Output

for each test case print "Case #i:" in a line first, i means the case number. Then print a list that contains all the paid person and his chosen test center in the "student_name test_center_name" form, one item per line. the list should be sorted in alphabetical order according to student_name. print a blank line after each test case

Sample Input
6 1 100
10  REG INFINITE_Li 
20  GET INFINITE_Li    HUST
120 PAY INFINITE_Li
210 REG frederic
220 GET frederic       HUST
319 PAY frederic

8 1 100
10  REG INFINITE_Li 
20  GET INFINITE_Li    HUST
119 PAY INFINITE_Li
210 REG frederic
220 GET frederic       HUST
315 CAL frederic
316 GET frederic       HUSTCS
319 PAY frederic

12 2 1000
10 REG frederic
20 REG amamiya_yuuko
30 GET amamiya_yuuko   otoha
40 REG miyamura_miyako
50 GET miyamura_miyako otoha
60 GET frederic        otoha
70 REG yuri   
80 GET yuri            SSS
90 PAY frederic
100 PAY amamiya_yuuko
110 PAY miyamura_miyako 
120 PAY yuri
Sample Output
Case #1:
frederic HUST

Case #2:
INFINITE_Li HUST
frederic HUSTCS

Case #3:
amamiya_yuuko otoha
miyamura_miyako otoha
yuri SSS
Hint

Source
Hust Monthly 10.04.05/INFINITE_Li