Declaration of Content

Time limit1sMemory limit128 MB

Summary

For each product, derive tight lower and upper percentage bounds for every listed ingredient from its ordering and optional exact percentages, then answer queries asking which products maximize or minimize a given ingredient's possible amount.

Level: Medium6 of 10
Topics: Greedy, Math, Simulation
Solved: No attempts yet

Problem

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 \le P \le 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 \le n \le 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 a space, an integer $p$ , $0 \le p \le 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 \le Q \le 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.

Examples1

Example 1

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

Expected output

Product_1
Product_3
Product_2 Product_3
Product_1 Product_2 Product_3