4043번 - We’ve Got Chemistry, Babe 다국어

Barry Liam is a chemistry student at Uranium University (good ol’ UU), and does pretty well except in one area — balancing chemical equations. As I’m sure you recall from your last chemistry class, a chemical reaction can be represented by a chemical equation, with the reactants on the left and the products on the right, separated by an arrow. For example, the chemical equation to form aluminum oxide out of aluminum and oxygen is

Al + O₂ → Al₂O₃.

However, the above equation is not balanced - there is one aluminum (Al) atom on the left hand side and two on the right, and there are two oxygen (O) atoms on the left and three on the right. A properly balanced version of this equation would be:

4Al + 3O₂ → 2Al₂O₃.

Note that not only are all the coefficients positive integers, but the greatest common divisor of all of them is 1 (two requirements when balancing). While Barry understands all this, he is flummoxed when asked to do it, especially when asked to balance equations such as:

Fe₂(SO₄)₃ + KSCN → K₃Fe(SCN)₆ + K₂SO₄.

Notice here that atoms in parentheses are all multiplied by the number that follows (so in this equation there are 12 oxygen atoms on the left and six carbon (C) atoms on the right, for example). Also, a symbol appears at most once in any reactant or product. Barry would like to ask his roommate for help, but he’s a Ballet major who thinks balancing equations have something to do with dancing en pointe (actually, he thought Barry said “Balanchine equations”). I guess Barry will have to look for a new major, unless you can help him.

Each test case will consist of a single line starting with two positive integers r and p indicating the number of reactants and products (the maximum value for each is 10). There will then follow the r reactants. Each reactant will consist of one or more terms, where each term is either a single chemical symbol, a single chemical symbol followed by an integer ≥ 2, or a set of parentheses around a term, followed by an integer ≥ 2. All chemical symbols consist of one or two alphabetic characters, only the first of which is capitalized. Following the r reactants will be the p products which follow the same rules as the reactants. There will be no more than 20 different chemical symbols in any test case. A line containing two zeros will terminate the input.

For each test case, you should output the appropriate coefficients needed to balance the equation, listed in the order that the reactants and products are given. Use a single space to separate the values, and preface each with the case number, using the format shown below. If an equation cannot be balanced correctly or uniquely (see the last sample input, which has solutions 1 2 1 1, 1 3 1 2, 1 4 1 3, etc.), you should output the word No.