Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Declaration of Content
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 546 Accepted: 143

Description

Most food you can buy at your local grocery store has a declaration of content. The declaration of content lists the ingredients of the product. It does not necessarily tell you the exact amount of every ingredient, only the ordering of the ingredients, from most common to least common. For some ingredients, an exact percentage might be given, either required by law or because the producer wants you to know how much of the fine expensive ingredients they have used. Given a set of different products and their respective declarations of content you should determine which contain the most or the least of some given ingredients. For simplicity, we assume in this problem that the percentage of each ingredient always is an integer.

Input

The input consists of several test cases. Each test case consists of two parts.

The first part of a test case begins with an integer P, 1 ≤ P ≤ 10, the number of different products in this test case, on a line of its own. Then follows the description of the P products. Each product description consists of a line giving the name of the product, followed by a line containing an integer n, 1 ≤ n ≤ 100, giving the number of ingredients in this product. Then follow n lines, the i:th of which contains the name of the i:th most common ingredient of the product. In case of ties, the ingredients will be listed in arbitrary order. Optionally, every ingredient name can be followed by space, an integer p, 0 ≤ p ≤ 100 and a percentage sign. If this is present, it specifies the exact amount of this ingredient in the product. Otherwise, because all percentages in this problem are integers, the ingredient makes up at least one percent of the total product.

The second part of a test case begins with an integer Q, 1 ≤ Q ≤ 100, the number of queries. Then follow Q lines, each containing a query. A query is of the form "least X", or "most X", where X is the name of an ingredient. In the "most X" case, the ingredient X is guaranteed to be present in at least one of the products.

A name of a product or an ingredient is a string of alphabetic characters (A-Z and a-z), digits (0-9) and underscore. Case is significant. No name will be longer than 30 characters. You may assume that each declaration of content is valid.

The last test case to be processed is followed by a line consisting of the integer 0.

Output

The output consists of one line for every query in the input data. For each query, output the name of the product containing the most or the least of ingredient X, as indicated by the query. If there are several possible such products, output all of them, in the same order as the products were presented in the test case input data. The product names should be separated by a single space.

Sample Input

```3
Product_1
3
A
B
C
Product_2
3
C
B
A
Product_3
2
B
C 35%
4
most A
most B
most C
least D
0```

Sample Output

```Product_1
Product_3
Product_2 Product_3
Product_1 Product_2 Product_3
```

Source

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