Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
66 - The 5th Zhejiang Provincial Collegiate Programming Contest - 1009
Intelligent Pouring Robot

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Do you like pouring on Internet forums?

In fact pouring is translated from the Chinese word Guan Shui, and it is similar to bump or spamming in English, which means posting messages that have no meaning at all. However, IMHO (in my humble opinion) the word pouring means much more than bump and spamming: it may refer to any posts on the forums except those most serious ones. So it is not surprising to see that many students like pouring very much and spend a lot of time pouring every day. Of course you're one of them.

One day you think it is sometimes tedious to pour with your friends in a fixed way. For example, if someone posts a message containing the word bg, e.g. "gxgx, bgbg", the following posts are usually "pt". Those tedious works can be easily done by programs, why do you need to do it yourself? Then you decide to write a program named "pouring robot" that can do pouring for you automatically. So you can save the time spent in pouring, while your friends will still see "your" pouring and your post count will still increase every day.

As a good developer, you always maximize the flexibility and reliability of every program you make. In order to make the pouring robot have different behaviors when it is used by different users, its behavior should be defined in the configuration files provided by the users. The basic working logic of the pouring robot is: it refreshes the forum every second to retrieve the new posts, and every time it sees a post from others it will post a particular reply message several seconds later with two exceptions (which will be discussed later). Note that the robot will keep on retrieving new posts even when there's pending message to be posted. The user can use an XML (EXtensible Markup Language) file to specify the behavior of the robot. The DTD (Document Type Definition) schema used to define the configuration file is:

<!DOCTYPE config [

<!ELEMENT config (rule*,default)>
<!ELEMENT rule (keyword,(reply|noreply)+)>
<!ATTLIST rule interval CDATA #IMPLIED>
<!ATTLIST rule wait CDATA #IMPLIED>
<!ELEMENT default ((reply|noreply)+)>
<!ATTLIST default interval CDATA #REQUIRED>
<!ATTLIST default wait CDATA #REQUIRED>
<!ELEMENT keyword (#PCDATA)>
<!ELEMENT reply (#PCDATA)>
<!ELEMENT noreply EMPTY>

]>

If you're not familiar with DTD or XML, here is a simple example of the configuration file:

<config>
    <rule interval="10" wait="3">
        <keyword>bg</keyword>
        <reply>pt</reply>
    </rule>
    <rule>
        <keyword>pt</keyword>
        <noreply />
    </rule>
    <default interval="60" wait="10">
        <reply>...</reply>
        <reply>Boring...</reply>
    </default>
</config>

Where config is the root element of this file. It may contain zero or more rule elements and a default element. A rule element may contain an interval attribute and a wait attribute (both optional), a keyword element and one or more reply/noreply elements. A default element contains an interval attribute, a wait attribute, and one or more reply/noreply elements. A keyword/reply element only contains a text, and noreply element contains nothing. The value of interval/wait attribute is an integer, representing interval in seconds, while the corresponding value in default element is used for those rule elements that do not have the attribute. All the reply/noreply elements in a single rule/default element are the reply-list of this element.

When a new post if found, the robot will choose either the first rule whose keyword is found in the message (case insensitive), or the default one if none is found. Then choose a random element from its reply-list. If the chosen one is a reply element, the robot will post a message with its text wait seconds later. If the chosen one is a noreply element, the robot will do nothing. Another exception is, to prevent the user's account being banned by the moderator for frequent posting, the robot will cancel all replies that are to be posted less than interval seconds since the last reply. (E.g. if the last post is at 19:00:00 and the interval of the last post is 30 seconds, the robot will not post anything before 19:00:30) Note once the robot has decided to post a particular reply at postTime, all replies resulted by the following posts with reply time before postTime will also be canceled, even when posting it will not violate any interval values. (E.g. if the robot sees a post at 19:00:00 that matches the a rule with wait = 60, it will not reply another post at 19:00:10 that matches another rule with wait = 10 and interval = 10, although posting the latter reply first will not violate any interval values)

For example, the above configuration file indicates when a post containing "bg" is found, the robot will post "pt" 3 seconds later. And if a post contains neither "bg" nor "pt" is found, the robot will post either "..." or "Boring..." 10 seconds later if it does not violate the interval rule of the last post.

Note: Use the following method to produce identical sequences of random numbers: nextNum = (nextNum * 32771 + 12347) mod 32768. Where nextNum is the next random number generated (initialized to 1 every time the robot starts), and A mod B means the remainder of A / B. You can use the following C code in a 32-bit C/C++ compiler (or change int to the corresponding 32-bit integer type in your compiler) directly:

int nextNum;
int genRand() {
    nextNum = (nextNum * 32771 + 12347) % 32768;
    return nextNum;
}

Where nextNum should be initialized to 1 every time the robot starts. When choosing a random element in the reply-list, compute i = (genRand() mod listSize) + 1 and use the ith one (1-based) in the list, where listSize is the number of elements in the reply-list. Note that a random number is generated only when necessary (the interval of the last post will not be violated and listSize is more than one).

Input

Standard input will contain multiple test cases. The first line of the input is asingle integer T (1 <= T <= 100) which is the number of test cases. And it will be followed by T test cases.

There's a blank line before every case. Each test case contains two parts. The first part is the configuration XML file specified above. You can assume the XML file will always follow the DTD above and contains no other XML tags (e.g. comments). It will contain at most 50 rule elements, and every rule/default element will contain at most 50 reply/noreply elements. The value of interval/wait is always a positive integer no more than 3600. The text of every keyword/reply element will not be empty and will contain at most 255 characters other than '<' and line breaks.

The second part contains the posts on the forums (posted by others). It begins with an integer P (1 <= P <= 500), and P lines with the P posts in the format "hh:mm:ss message" followed. Where hh, mm, ss are the hour, minute and second parts (with potential leading zeros) of the post time of this post (0 <= hh <= 23, 0 <= mm <= 59, 0 <= ss <= 59), and message is the content of this post. The posts are sorted by their post times in ascending order. You can assume that no two posts will be posted at the same second and the interval between every two successive posts is less than 24 hours. message will not be empty and will contain at most 255 characters other than line breaks.

Output

For each test case, output the posts produced by the pouring robot in the same "hh:mm:ss message" format specified above.

Print a blank line between every two successive cases.

Sample Input

2

<config>
    <rule interval="10" wait="3">
        <keyword>bg</keyword>
        <reply>pt</reply>
    </rule>
    <rule>
        <keyword>pt</keyword>
        <noreply />
    </rule>
    <rule>
        <keyword>pia</keyword>
        <reply>anti-pia</reply>
    </rule>
    <default interval="60" wait="10">
        <reply>...</reply>
        <reply>Boring...</reply>
    </default>
</config>
5
10:20:15 gxgx, bgbg
10:22:05 pt2
10:30:00 Pia to Mars!
11:24:36 Is anyone in?
11:26:25 What're you doing?

<config>
    <rule>
        <keyword>ban</keyword>
        <noreply />
        <reply>I'm sorry, I won't do it again.</reply>
    </rule>
    <default interval="10" wait="1">
        <reply>...</reply>
        <noreply />
        <reply>...</reply>
    </default>
</config>
6
13:21:46 Could you tell me how to solve this problem?
13:23:22 I know it is not good to discuss the problems during a contest, but it is really too difficult for me.
13:24:13 Hey! Say something other than dots.
13:25:32 If you keep on pouring like this, I'll ask the moderator to ban you.
13:26:37 Well, now can you say something about this problem?
13:27:01 -___-

Sample Output

10:20:18 pt
10:30:10 anti-pia
11:24:46 ...
11:26:35 Boring...

13:21:47 ...
13:23:23 ...
13:24:14 ...
13:25:33 I'm sorry, I won't do it again.
13:26:38 ...

Author: XIAO, Dong


Submit    Status