화학자의 수학

문제

보통 고등학교 화학 시간에는 화학 반응식을 배운다. 이 식은 다음과 같이 생겼다.

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

위의 식 (1)~(3)은 모두 좌변과 우변의 균형이 맞추어져 있다. 하지만 아래 반응식은 그렇지 않다.

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

모든 화학 반응식은 질량 보존의 법칙을 지켜야 한다. 즉, 각 원소(H, O, Ca, Al, ...)의 개수는 화학 반응으로 변하지 않아야 한다. 따라서 좌변과 우변의 분자 개수를 맞추어 주어야 한다.

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

반응식 (6)의 계수는 왼쪽부터 오른쪽까지 (4, 3, 2)이고, 반응식 (7)의 계수는 (1, 5, 3, 4)이다. 계수가 1인 경우에는 생략할 수 있다.

올바른 화학 반응식의 계수는 다음 조건을 만족한다.

계수는 모두 양의 정수이다.
계수는 서로소이다. 즉, 계수들의 최대공약수는 1이다.
모든 원소에 대해 좌변의 양과 우변의 양이 같다.

위 세 조건을 모두 만족하는 화학 반응식을 올바른 화학 반응식이라고 한다. 화학에서 실제로 일어날 수 없는 반응이거나 존재하지 않는 분자가 등장하더라도, 이 문제에서는 올바른 화학 반응식으로 본다. (H2 → H2도 올바른 반응식이다.)

조건 1과 3만 만족하는(조건 2는 필수가 아닌) 화학 반응식은 균형 반응식이라고 부른다.

반응식 (4), (5)처럼 계수가 없는 화학 반응식이 주어졌을 때, 계수를 올바르게 구하는 프로그램을 작성하시오.

모든 올바른 화학 반응식의 계수가 유일하게 결정되는 것은 아니다. 예를 들어, H2O와 NH3를 생성하는 반응식이 다음과 같다고 하자.

xH2 + yO2 + zN2 + uH2 → vH2O + wNH3

이 경우 $(x, y, z, u, v, w) = (2, 1, 1, 3, 2, 2)$가 답이 된다. 하지만 $(4, 2, 1, 3, 4, 2)$나 $(4, 2, 3, 9, 4, 6)$도 올바른 정답이 된다. 그러나 이 문제에서 주어지는 모든 화학 반응식의 계수는 유일하게 결정된다.

입력

입력은 여러 개의 계수가 없는 화학 반응식으로 이루어져 있다.

화학 반응식은 다음과 같이 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>

모든 화학 반응식의 끝에는 마침표(.)가 붙는다. 예를 들어, 다음 반응식이 있을 때

Ca(OH)2 + CO2 → CaCO3 + H2O

입력으로는 다음과 같이 주어진다.

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

모든 화학 반응식의 길이는 80자를 넘지 않는다. <number>는 BNF에 따라 한 자리 또는 두 자리 정수이므로 1 이상 99 이하이다. 괄호는 중첩해서 사용되지 않는다. 화학 반응식의 각 변은 최대 10개의 분자로 이루어진다. 또한 계수는 항상 40,000을 넘지 않는다.

입력의 마지막 줄에는 마침표(.)가 하나 주어진다.

<chemical_element>로 주어지는 화학 원소 중에는 존재하지 않는 원소나 아직 발견되지 않은 원소가 있을 수 있다. 또, 우눈옥튬(Uuo, 118번)처럼 원소 기호가 알파벳 세 글자인 경우는 주어지지 않는다.

출력

각각의 화학 반응식에 대해서, 그 반응식을 올바르게 만드는 계수를 공백으로 구분하여 출력한다.