The Chemist's Mathematics

In high-school chemistry class you usually learn chemical equations. They look like this.

(1) 2H2 + O2 → 2H2O
(2) Ca(OH)2 + CO2 → CaCO3 + H2O
(3) N2 + 3H2 → 2NH3

Equations (1) through (3) above are all balanced between the left-hand side and the right-hand side. The equations below, however, are not.

(4) Al + O2 → Al2O3
(5) C3H8 + O2 → CO2 + H2O

Every chemical equation must obey the law of conservation of mass. That is, the count of each element (H, O, Ca, Al, ...) must not change through the reaction. Therefore the numbers of molecules on the two sides must be balanced.

(6) 4Al + 3O2 → 2Al2O3
(7) C3H8 + 5O2 → 3CO2 + 4H2O

The coefficients of equation (6) are, from left to right, (4, 3, 2), and those of equation (7) are (1, 5, 3, 4). A coefficient of 1 may be omitted.

The coefficients of a correct chemical equation satisfy the following conditions.

1. All coefficients are positive integers.
2. The coefficients are coprime; that is, their greatest common divisor is 1.
3. For every element, the amount on the left-hand side equals the amount on the right-hand side.

A chemical equation that satisfies all three conditions is called a correct chemical equation. Even if the reaction cannot actually occur in chemistry or a non-existent molecule appears, it is still a correct chemical equation for this problem. (H2 → H2 is also a correct equation.)

A chemical equation that satisfies conditions 1 and 3 (condition 2 not being required) is called a balanced equation.

Given a chemical equation without coefficients, such as equations (4) and (5), write a program that computes the correct coefficients.

The coefficients of a correct chemical equation are not always uniquely determined. For example, suppose an equation producing H2O and NH3 is as follows.

xH2 + yO2 + zN2 + uH2 → vH2O + wNH3

In this case $(x, y, z, u, v, w) = (2, 1, 1, 3, 2, 2)$ is an answer. But $(4, 2, 1, 3, 4, 2)$ and $(4, 2, 3, 9, 4, 6)$ are also correct answers. However, the coefficients of every chemical equation given in this problem are uniquely determined.

The input consists of several chemical equations without coefficients.

A chemical equation can be described by the following BNF.

<chemical_equation> ::= <molecule_sequence> "->" <molecule_sequence>
<molecule_sequence> ::= <molecule> | <molecule> "+" <molecule_sequence>
         <molecule> ::= <group> | <group> <molecule>
            <group> ::= <unit_group> | <unit_group> <number>
       <unit_group> ::= <chemical_element> | "(" <molecule> ")"
 <chemical_element> ::= <uppercase_letter>
                      | <uppercase_letter> <lowercase_letter>
 <uppercase_letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I"
                      | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R"
                      | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z"
 <lowercase_letter> ::= "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i"
                      | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r"
                      | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
           <number> ::= <non_zero_digit>
                      | <non_zero_digit> <digit>
   <non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
            <digit> ::= "0" | <non_zero_digit>            

Every chemical equation ends with a period (.). For example, given the equation

Ca(OH)2 + CO2 → CaCO3 + H2O

it is given in the input as follows.

Ca(OH)2+CO2->CaCO3+H2O.

The length of every chemical equation does not exceed 80 characters. By the BNF, a <number> is a one- or two-digit integer, so it is between 1 and 99. Parentheses are not nested. Each side of a chemical equation consists of at most 10 molecules. Also, coefficients never exceed 40,000.

The last line of the input contains a single period (.).

Among the chemical elements given as <chemical_element>, there may be elements that do not exist or have not yet been discovered. Also, elements whose symbol is three letters, such as ununoctium (Uuo, number 118), are not given.

For each chemical equation, output the coefficients that make the equation correct, separated by spaces.