Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3214
Bussiness Rules Management System

Time Limit: 2 Seconds      Memory Limit: 32768 KB

Sean is an energetic guy working in a leading software company. These days around, his team is assigned the task of building a Business Rules Management System (BRMS). A BRMS is a rule based inference engine, you know, to make a machine think like a human. One of the core modules, which Sean taking responsible for, is the agenda module.

A rule based inference engine has a set of rules and a set of facts which is dynamically changing. A rule is said to be activated if its conditions are satisfied by these facts. As facts are added to and deleted from the system, rules get activated or deactivated. A rule also has a priority associated with it.

The agenda module maintains currently activated rules. It supports three commands:

  • add RuleName: Add an activated rule to the agenda. It is guaranteed that the specified rule is not currently in the agenda.
  • delete RuleName: Delete a deactivated rule from the agenda. It is guaranteed that the specified rule is currently in the agenda.
  • getActivation: Return the name of the activated rule with the highest priority. If there are several activated rules with the same highest priority, return the rule which is most recently added to the agenda. The returned rule is also removed from the agenda.

Note that in a well designed BRMS, there are no more than 10 different priorities for rules in a system. You can thus assume that the rules you are going to deal with do not use more than 10 different priorities.

Now Sean is planning to go on a vacation with his family. He needs you to help him finish this module when he is on leave.

Input

The first line of the input is an integer T (T≤50), the number of cases.

In the first line of each case is an integer R (1≤R≤10000), the number of rules in the system. Next R lines each describes a single rule, containing the name of the rule and its priority, separated by a single space. The names consist of lowercase alphabetic characters ('a'-'z'), digits ('0'-'9') and hyphens ('-') only, with their lengths between 1 and 20 inclusive. Priorities are integers in the range [-10000, 10000]. No two rules have the same name.

Next is an integer M (M≤30000), the number of commands to your agenda module. Next M lines each describes a command. Each command starts with a single character from the set {a,d,g}, representing the commands add, delete, and getActivation respectively. If this character is a or d, then it is followed by a single space and the name of the rule being activated or deactivated. It is guaranteed that this name refers to an existing rule.

Cases are separated by one blank line.

Output

For each getActivation command, output the name of the rule this command should return. If there is currently no activated rule in the agenda, output <empty>. The output for each getActivation command should be on a separate line.

Sample Input

2
3
r1 1
r2 2
r3 3
6
a r3
a r2
a r1
g
d r2
g

3
business-starts 1
client-arrives 1
emergency-occurs 2
8
g
a business-starts
a client-arrives
a emergency-occurs
g
g
g
g

Sample Output

r3
r1
<empty>
emergency-occurs
client-arrives
business-starts
<empty>


Author: LIU, Xin
Source: ZOJ Monthly, June 2009
Submit    Status