Woburn Challenge 2002

Problem 3: The Big Book of Recipes

So how is the monkeys' meeting going, you ask? Well, the Head-Monkey is quite big on food and whenever there's a meeting atop the Enchanted Tree, it is a necessity that dinner is served (pun intended). What the monkeys don't realize is that the Head-Monkey is not really a good cook. But then, how many army leaders are good cooks? The answer is, none. This time, the Head-Monkey has purchased a cookbook. The cookbook has a certain number of recipes, but any recipe may require an ingredient which must be prepared according to some other recipe! This is all quite confusing for the Head-Monkey. She wants you to tell her how much of each base ingredient she needs for her recipe.

Input

The first line of input contains a single integer, T (1 ≤ T ≤ 50), indicating the number of test cases.
The first line of each test case will contain N (1 ≤ N ≤ 20), the total number of ingredients to follow. For each ingredient, there follows a line with that ingredients name - if the ingredient is a basic ingredient it will be in lowercase letters, if there is a recipe in terms of other ingredients for it, its name will be in capital letters.
For each non-basic ingredient, a recipe for one serving of that ingredient will follow (format: an integer k, 1 ≤ k ≤ 20, indicating the number of ingredients in that recipe, then a series of lines of the form [number of servings of ingredient required, _space_, ingredient required]).
Finally, there will be an ingredient name - you are to determine the amount of each basic ingredient required to make one serving of that ingredient.

Output

A series of lines of the form [number of servings of ingredient required, _space_, ingredient required], containing only basic ingredients. Output them in the same order as they were listed in the input.
Leave a blank line between test cases.

Sample Input

1
10
CHEESE
milk
SAMMICH
salt
turkey
ham
egg
vinegar
MAYO
bread
2
1.5 milk
0.25 salt
5
2.2 CHEESE
1 bread
1 turkey
1 ham
0.3 MAYO
3
0.2 egg
0.1 vinegar
0.1 salt
SAMMICH

 












[recipe for CHEESE]


[recipe for SAMMICH]





[recipe for MAYO]



[thing we want to make]

Sample Output

3.3 milk
0.58 salt
1 turkey
1 ham
0.06 egg
0.03 vinegar
1 bread

Note: The comments off to the side won't appear in the input file!

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

"The first line of input contains a single integer, T (1 ≤ T ≤ 50), indicating the number of test cases."

I presume the first line in the sample input should contain the integer 1?