Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
The Downloading Task
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 1382Accepted: 357

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.

 

Sample Input

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

Sample Output

name downloading

B finished
a paused
b downloading

ee downloading
dd waiting
cc finished
bb paused
aa downloading

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator