The Downloading Task
Description
A download software can execute multiple tasks simultaneously. For each task, there might be four states: downloading, waiting, paused, or finished. And there can be at most n tasks with state downloading at the same time. At the very beginning, the software has no tasks. Then it will receive m pieces of instructions. The forms of instructions are as listed below:
- Sort asc: Set the priority in ascending order. The smallest name (in alphabet order) has the highest priority. This is the initial order.
- Sort desc: Set the priority in descending order. The biggest name (in alphabet order) has the highest priority.
- New A: Create a new task A. If the tasks with downloading state are less than n, set A's state with downloading, otherwise waiting.
- Pause A: Set the task A with state paused. And change the task of waiting state (if there is one) with the highest priority into a downloading state.
- Continue A: If the tasks with downloading state are less than n, set A with downloading, otherwise waiting.
- Finish A: Set the task A with state finished. And change the task of waiting state (if there is one) with the highest priority into a downloading state.
Now you need to program to simulate the download software, output the state of all the tasks according to the final priority after it has executed all the m pieces of instructions.
Assumption: Any two different tasks have different names. The task described in the New instruction has never existed before. The task described in the Pause instruction is either waiting or downloading. The task described in the Continue instruction is paused. The task described in the Finish instruction is downloading.
Input
The first line of the input is an integer T which indicates the number of test cases. For each test case, the first line are two integers n (1 ≤ n ≤ 10000) and m (1 ≤ m ≤ 100000), then m lines of instructions in the forms as described above. In the instructions, names are strings contain either letters or figures with length no greater than 10.
n m
instruction[1]
instruction[2]
...
instruction[m]
Output
For each test case, output all the tasks' states according to the final priority, each task a line. Print a blank line after each test case.
3
10 1
New name
1 5
New a
New b
New B
Pause a
Finish B
2 10
New aa
New bb
New cc
Pause aa
New dd
Continue aa
New ee
Finish cc
Sort desc
Pause bb
name downloading
B finished
a paused
b downloading
ee downloading
dd waiting
cc finished
bb paused
aa downloading
Source
South Central China 2008 hosted by NUDT