Balance chemical equations! Bernd is a high school student who has some problems in chemistry. In class he has to design chemical equations for some experiments they are doing, such as the combustion of heptane:


  C7H16 + 11O2 → 7CO2 + 8H2O


Since mathematics isn't exactly Bernd's strongest subject, he often has a hard time finding the exact ratios between the pro- and educts of the reaction. Since you are Bernd's tutor, it is your job to help him! Write a program, that calculates the amount of each substance needed to get a valid chemical equation.

Input

The input is a chemical equation without amounts. In order to make this possible in pure ASCII, we write any subscriptions as ordinary numbers. Element names always start with a capital letter and may be followed by a minuscule. The molecules are separated with + signs, an ASCII-art arrow -&gt; is inserted between both sides of the equation:

Al+Fe2O4-&gt;Fe+Al2O3


The input is terminated with a newline and won't contain any spaces. If the input is invalid, your program may do whatever you like.

You may assume, that the input is never longer than 1024 characters. Your program may either read the input from standard input, from the first argument or in an implementation defined way at runtime if neither is possible.

Output

The output of your program is the input equation augmented with extra numbers. The number of atoms for each element must be the same on both sides of the arrow. For the example above, a valid output is:

2Al+Fe2O3-&gt;2Fe+Al2O3


If the number for a molecule is 1, drop it. A number must always be a positive integer. Your program must yield numbers such that their sum is minimal. For instance, the following is illegal:

40Al+20Fe2O3-&gt;40Fe+20Al2O3


If there is no solution, print

Nope!


instead. A sample input that has no solution is

Pb-&gt;Au


Rules


This is code-golf. The shortest code wins.
Your program must terminate in reasonable time for all reasonable inputs.


Test Cases

Each test case has two lines: An input and a correct output.

C7H16+O2-&gt;CO2+H2O
C7H16+11O2-&gt;7CO2+8H2O

Al+Fe2O3-&gt;Fe+Al2O3
2Al+Fe2O3-&gt;2Fe+Al2O3

Pb-&gt;Au
Nope!
C, 442 505 chars

// element use table, then once parsed reused as molecule weights
u,t[99];

// molecules
char*s,*m[99]; // name and following separator
c,v[99][99]; // count-1, element vector

i,j,n;

// brute force solver, n==0 upon solution - assume at most 30 of each molecule
b(k){
    if(k&lt;0)for(n=j=0;!n&amp;&amp;j&lt;u;j++)for(i=0;i&lt;=c;i++)n+=t[i]*v[i][j]; // check if sums to zero
    else for(t[k]=0;n&amp;&amp;t[k]++&lt;30;)b(k-1); // loop through all combos of weights
}

main(int r,char**a){
    // parse
    for(s=m[0]=a[1];*s;){
        // parse separator, advance next molecule
        if(*s==45)r=0,s++;
        if(*s&lt;65)m[++c]=++s;
        // parse element
        j=*s++;
        if(*s&gt;96)j=*s+++j&lt;&lt;8;            
        // lookup element index
        for(i=0,t[u]=j;t[i]-j;i++);
        u+=i==u;
        // parse amount
        for(n=0;*s&gt;&gt;4==3;)n=n*10+*s++-48;
        n+=!n;
        // store element count in molecule vector, flip sign for other side of '-&gt;'
        v[c][i]=r?n:-n;
    }
    // solve
    b(c);
    // output
    for(i=0,s=n?"Nope!":a[1];*s;putchar(*s++))s==m[i]&amp;&amp;t[i++]&gt;1?printf("%d",t[i-1]):0;
    putchar(10);
}


Run as:

./a.out "C7H16+O2-&gt;CO2+H2O"
./a.out "Al+Fe2O4-&gt;Fe+Al2O3"
./a.out "Pb-&gt;Au"


Results:

C7H16+11O2-&gt;7CO2+8H2O
8Al+3Fe2O4-&gt;6Fe+4Al2O3
Nope!