Chemistry

Balancing a chemical equation is the part of chemistry that gives students the most trouble. Write a program that balances one for them.

A chemical equation is given in this form.

<equation> = <side> "=" <side>
<side>     = <summand> ["+" <summand>]...
<summand>  = <factor> [<factor>]...
<factor>   = <capital letter> <run of lowercase letters> [<one digit>]

One example of a chemical equation is N2+H2=NH3. A digit inside a factor gives the amount of the matching substance in that summand. When the digit is omitted, the amount is 1. The summand on the right side of the equation above holds 1 unit of the substance N and 3 units of the substance H.

Your task is to find an integer coefficient for every summand so that the equation becomes balanced, that is, so that the total amount of each substance on the left side equals the total amount of the same substance on the right side. One balanced form of the example equation is N2+3H2=2NH3.

When a summand gets the coefficient $A$ and that summand contains $B$ units of some substance, the summand brings $A \times B$ units of the substance into the equation. The total amount of a substance on one side of the equation is the sum of the units brought by every summand on that side.

The first and only line contains the chemical equation to balance. Its length is at most 100. Only letters of the English alphabet and the digits 1 to 9 appear in it, and there are no spaces.

The number of distinct substances in the whole equation is smaller than 10.

A substance appears in at most one factor of each summand, so summands such as CHOH2 never occur.

The input always admits a balanced assignment whose coefficients are not all zero, and every coefficient defined in the output section is at most $10^9$ in absolute value.

Print the coefficient of every summand on the first and only line, in the order in which the summands appear in the equation, separated by single spaces. The coefficients are integers, and a negative coefficient means that the matching summand belongs on the other side of the equation.

Several coefficient vectors can balance the same equation, so print the one that the following rule picks out. Number the summands $1$ to $k$ in the order they appear, the left side first. For summand $j$, let $c_j$ be the vector that holds, for each substance of the equation, the amount of that substance in summand $j$, written with a plus sign when summand $j$ sits on the left side and with a minus sign when it sits on the right side. Coefficients $x_1, \dots, x_k$ balance the equation exactly when $x_1 c_1 + x_2 c_2 + \dots + x_k c_k$ is the zero vector.

Call summand $j$ free when $c_j$ is a linear combination of $c_1, \dots, c_{j-1}$, and call it fixed otherwise. Summand $1$ is always fixed, because $c_1$ is never the zero vector. Exactly one rational solution gives the coefficient $1$ to every free summand. Multiply that solution by a nonzero rational number so that all coefficients become integers, the greatest common divisor of the coefficients is $1$, and the first nonzero coefficient is positive. Exactly one vector meets those three conditions, and that vector is the answer.