화학

화학 반응식의 계수를 맞추는 일은 화학 수업에서 학생들이 가장 어려워하는 부분이다. 이 일을 대신 처리하는 프로그램을 작성하자.

화학 반응식은 다음 형태로 주어진다.

<반응식> = <변> "=" <변>
<변>     = <항> ["+" <항>]...
<항>     = <인자> [<인자>]...
<인자>   = <대문자> <소문자 나열> [<한 자리 숫자>]

화학 반응식의 예로 N2+H2=NH3이 있다. 인자 안에 숫자가 있으면 그 숫자가 해당 항에 들어 있는 물질의 양을 뜻하고, 숫자가 없으면 양은 1이다. 위 반응식의 오른쪽 항에는 물질 N이 1만큼, 물질 H가 3만큼 들어 있다.

각 항 앞에 정수 계수를 하나씩 붙여 반응식의 양변을 맞춰야 한다. 즉 모든 물질에 대해 왼쪽 변의 총량과 오른쪽 변의 총량이 같아야 한다. 예시 반응식을 맞춘 형태 하나는 N2+3H2=2NH3이다.

어떤 항의 계수가 $A$이고 그 항이 어떤 물질을 $B$만큼 담고 있으면, 그 항은 반응식에 그 물질을 $A \times B$만큼 넣는다. 한 변에서 어떤 물질의 총량은 그 변의 각 항이 넣는 양을 모두 더한 값이다.

첫째 줄에 계수를 맞춰야 하는 화학 반응식이 주어진다. 길이는 100 이하이다. 영어 알파벳과 숫자 1부터 9까지만 나오며, 공백은 없다.

반응식 전체에 나오는 서로 다른 물질의 수는 10보다 작다.

한 항 안에서 같은 물질은 최대 한 인자에만 나온다. 따라서 CHOH2 같은 항은 주어지지 않는다.

계수가 모두 0은 아닌 해가 입력에 항상 존재하고, 출력 항목이 정하는 계수는 절댓값이 $10^9$ 이하이다.

첫째 줄에 각 항의 계수를 반응식에 나온 순서대로 공백 하나로 구분해 출력한다. 계수는 정수이고, 계수가 음수이면 그 항을 반대쪽 변으로 옮겨야 한다는 뜻이다.

같은 반응식을 맞추는 계수 조합이 여러 개 있을 수 있으므로, 다음 규칙이 고르는 조합을 출력한다. 왼쪽 변부터 순서대로 항에 $1$번부터 $k$번까지 번호를 붙인다. $j$번 항에 대해, 반응식에 나오는 각 물질이 그 항에 들어 있는 양을 모은 벡터를 $c_j$라 하자. 이때 $j$번 항이 왼쪽 변에 있으면 양을 그대로 쓰고, 오른쪽 변에 있으면 부호를 뒤집어 쓴다. 계수 $x_1, \dots, x_k$가 반응식을 맞추는 것은 $x_1 c_1 + x_2 c_2 + \dots + x_k c_k$가 영벡터인 것과 같다.

$c_j$가 $c_1, \dots, c_{j-1}$의 일차결합이면 $j$번 항을 자유 항이라 하고, 그렇지 않으면 고정 항이라 하자. $c_1$은 영벡터가 아니므로 $1$번 항은 항상 고정 항이다. 자유 항의 계수를 모두 $1$로 두는 유리수 해는 정확히 하나 있다. 그 해에 0이 아닌 유리수를 곱해서 모든 계수를 정수로 만들고, 계수의 최대공약수를 $1$로 만들고, 처음으로 0이 아닌 계수를 양수로 만든다. 이 세 조건을 함께 만족하는 벡터는 하나뿐이며, 그 벡터가 답이다.