As the Carnival period draws to an end, the remote Kingdom of Byteland is making preparations for the donut feast of Mardi Gras. The King's Court is eagerly anticipating the arrival of notable guests and crowned heads from all round the continent, who will partake of the ceremonial strawberry donut dinner in the Royal Halls. But this year, just before the feast is due to commence, disaster has struck: The Recipe for strawberry donuts, jealously guarded by the Lord Master of the Household, has been destroyed in a kitchen fire caused by an overturned frying pan!

Panic and dispair have spread through the King's Court. Without The Recipe, noone is able to fry a half-reasonable donut. The one hope of salvation is in an old, almost forgotten legend, which says that in a far-off part of Byteland, there lives a dynasty of Wicked Old Witches, who hold another copy of The Recipe, treasuring it and passing it on from mother to daughter. In a valiant effort to save the face of the Kingdom of Byteland, you set out on an expedition to find the Witches and their strawberry donut Recipe!

After climbing many hills and crossing many seas, you eventually reach a small village in which all of the legendary Witches dwell. The good news is that one copy of the Recipe is still in existance, and is held by one of the living witches. To make things even better, it turns out that the Witches are not as Wicked as the legend states: in fact, they are quite sociable, and may even help you locate the witch who has the Recipe. However, each witch will insist on telling you her life story first, before you can get any useful information out of her. And they are all Old Witches, so it may take a while, and you really don't want to interrupt a Witch when she is talking. Only after a Witch has recounted her countless tales, will she tell you what she knows about the recipe, which will be something along the following lines:

• "The recipe? Oh dear, I'm sorry, I've never seen it myself..." 
• "The recipe? Yes, I do remember... I had it once, many years ago, but I have since passed it on to my most talented daughter (and here comes the name of the daughter in question). Her cooking is so much better than mine, you know!"
• "The recipe? But why of course! Here it is. Just make sure you keep it safe!" (This is the answer you want to hear, but you will only hear it from the one Witch who has the recipe.)

Mardi Gras is drawing near, and you may sadly not have enough time to talk to all the charming Old Witches. Try to figure out a way to obtain the recipe, and to do it as quickly as possible! 

Input

The input starts with a single positive integer integer k, denoting the number of Witches in the dynasty (k < 10⁶). The next line starts with the name of the oldest Witch, from whom all the other Witches are descended, and who of course must have once held the recipe, even if she may perhaps not have it now. The input line describing this Witch is of the form:

Name chats x min.

Each of the next k-1 lines contains a description of a Witch, formatted as follows:

Name is the daughter of Mother's-Name and chats x min.

The number x describes the number of minutes of your time a Witch will take up if you talk to her: an integer between 1 and 10⁶. All names of witches are sequences of exactly 5 letters, starting with one upper-case letter (A-Z) and followed by 4 lower-case letters (a-z). The order of Witches at input is such that each Witch is described later than her mother. No two Witches in the dynasty share the same name.

Output

Your output should describe the strategy you adopt when talking to the witches, with a complete plan of action, stating who to approach in what order, depending on previously obtained answers.

First, print the name of the witch you approach as the first, followed by a list of clauses of the form ANSWER -> FURTHER_ACTION, one clause corresponding to each of the possible answers which may be given by the Witch. For every Witch, you should consider all possible answers the witch may give you, which are feasible given the information you have obtained so far from other Witches. For compactness, assume that in the case when a Witch directs you to her daughter, the ANSWER string is simply to be the name of the daughter in question. If the Witch answers that she has no idea of the recipe, the ANSWER string should be: NEVER. If a Witch tells you she has the recipe, no further action needs to be taken, and you shoud not write any text corresponding to such an answer in your output file. (In particular, if you can be sure that the Witch you have just asked has the recipe, you should not print text corresponding to any answers given by this Witch.) The ANSWER string should be followed by a description of FURTHER_ACTION to take, representing actions which you will subsequently take, subject to the given answer. The FURTHER_ACTION should be written down following the same grammar rules as those describing the whole of your program's output (i.e., this paragraph is to be read recursively). 

White spaces (spaces, newlines, and tabs), numbers, and punctuation marks may be inserted arbitrarily into your program's output to improve its formatting; they will be disregarded when testing your solution. The order in which you consider the possible answers of each Witch is arbitrary. 

In your strategy  you may never approach a Witch if, based on information received so far, you can be sure she does not have the recipe. You can assume that Witches always tell the truth, and should not print any text corresponding to the case of an answer which you already know may not occur. You can also safely assume that the recipe does not change hands while you are in the Witches' village.

Scoring

For each data set, the score of your program will be computed as the ratio of two integer values, t / T. Here, t denotes the number of minutes required for a conversation with the most talkative Witch in the dynasty, and T is the total amount of time your strategy takes to find the recipe for a worst-case scenario of answers.

Your program will be tested for multiple data files. The overall score of your program will be the average of scores obtained for individual data sets.

Notes

The time limit of your program for each data set is 10 seconds. Your program must not print more than 30MB of output text (whitespace included!). The number of Witches k will be approximately 10³ (for half of the tests) and approximately 10⁵ (for the remaining tests).

Example

Input:
5
Alice chats 20 min.
Betty is the daughter of Alice and chats 10 min.
Chloe is the daughter of Alice and chats 10 min.
Marie is the daughter of Chloe and chats 30 min.
Suzie is the daughter of Marie and chats 10 min.

Sample output 1:
1. Chloe:
   * "Marie!"
      2. Suzie:
         * "NEVER!"
            3. Marie.
   * "NEVER!"
      2. Alice:
         * "Betty!"
            3. Betty.

Score: 0.6

Explanation:

In the presented solution, you first approach Chloe and talk to her for 10 minutes.

If Chloe tells you she gave the recipe to her only daughter, Marie, then you next approach Suzie and talk to her for 10 minutes. If she does not have the recipe, then it must be with Marie; you talk to her next for 30 minutes, and obtain the recipe (after at most 50 minutes in total).

If Chloe tells you she has not seen the recipe, you next approach Alice. As the oldest witch, Alice must have seen the recipe, and if she doesn't have it, she must have given it to Betty. Talking to Alice takes up 20 minutes of your time, and talking to Betty takes up another 10 minutes. In this case, you will obtain the recipe after at most 40 minutes.

The score of your program is the time required to talk to the most talkative witch in the dynasty, Marie, divided by the worst-case time needed to obtain the recipe in the provided solution, i.e., 30/50.

Sample output 2:
1. Alice:
   * "Chloe!"
      2. Chloe:
         * "Marie!"
           3. Marie:
              * "Suzie!"
                 4. Suzie.
   * "Betty!"
      2. Betty.

Score: 0.429

Sample output 3:
1. Alice:
   * "Chloe!"
      2. Betty:
etc.

Evaluation: Wrong Answer.

Note that once you know the Recipe is in Chloe's part of the family, it cannot be with Betty.

Sample output 4:
1. Alice:
   * "Chloe!"
      2. Chloe:
         * "NEVER!"
etc.

Evaluation: Wrong Answer.

Note that once you know the Recipe has passed through Chloe's hands, it must either be with her or with one of her daughters.

Sample output 5:
Chloe Marie Suzie NEVER Marie NEVER Alice Betty Betty

Score 0.6

This solution is completely equivalent to Sample output 1.