Gold Rush
Petya, the alchemist, has created the philosopher's stone, which allows him to perform various alchemical reactions to transform substances into others. Each substance involved in a reaction, both the one being transformed and the resulting substances, has a mass of exactly one gram. Petya is unaware of the law of conservation of mass, so it may not apply here.
Petya starts with one gram of lead. Using the philosopher's stone, he can transform this lead into other substances, which can also be transformed further using the philosopher's stone. Petya's goal is to produce as much gold as possible through a series of these alchemical reactions.
Your task is to write a program that calculates the maximum amount of gold Petya can produce, based on the given descriptions of the alchemical reactions possible with the philosopher's stone.
Input
The first line of the input contains an integer K – the number of different substances involved in the alchemical reactions (1 ≤ K ≤ 6). The second line lists the names of these substances, separated by spaces, and must include lead ("svinec") and gold ("zoloto"). Each substance name is no longer than 10 characters.
The third line contains an integer L – the number of reaction types available (1 ≤ L ≤ 100). Following this are L descriptions of these reactions. Each reaction is described over two lines: the first line specifies the substance being transformed, and the second line lists the substances produced by the reaction.
Output
Your program should output a single integer representing the maximum grams of gold Petya can produce, or the message "QUANTUM SATIS" (Latin for "As much as needed") if Petya can produce an unlimited amount of gold.