Chemical Equation Balancing

You are given an unbalanced chemical equation in the form of a string. The chemical equation is written as:

Compound₁+Compound₂+⋯=Compound_k+Compound_k+1+⋯

Each compound is represented by its chemical formula (e.g. H2O, CO2, C16H18O9). Note that different characters (like the letter O and the digit 0) are distinct.

Your task is to add a positive integer coefficient before each compound so that the equation is balanced, i.e. the number of atoms of each element is equal on both sides. In mathematical terms, if the coefficients are \(a_1,a_2,\dots,a_n\) and the number of atoms of element \(E\) in compound \(i\) is \(n_{i}(E)\), then the following conservation law must hold for every element \(E\):

\(\displaystyle \sum_{i=1}^{k} a_i\,n_{i}(E) = \sum_{i=k+1}^{n} a_i\,n_{i}(E)\)

Output the balanced equation as a string where each compound is preceded immediately by its coefficient (even if it is 1). The operators '+' and '=' should appear exactly as in the input.

Example:

For the input

C16H18O9+O2=CO2+H2O

the balanced equation is

1C16H18O9+16O2=16CO2+9H2O

inputFormat

A single line containing the unbalanced chemical equation.

The equation is given in the format: Compound1+Compound2+...=Compound(k+1)+Compound(k+2)+...

outputFormat

Output a single line — the balanced chemical equation. Each compound should be preceded by its positive integer coefficient.

sample

C16H18O9+O2=CO2+H2O

1C16H18O9+16O2=16CO2+9H2O