The chemical formula of a molecule M describes its atomic make-up. Chemical formulas obey the following grammar:

M := G | M G

G := S | S C

S := A | '(' M ')'

C := T | N E

E := D | D E

T := '2' | ... | '9'

N := '1' | ... | '9'

D := '0' | .. | '9'

A := U | U L | U L L

U := 'A' | .. | 'Z'

L := 'a' | .. | 'z'

The count C represents a multiplier for the subgroup S that precedes it. For example, H2O has two H (hydrogen) and one O (oxygen) atoms, and (AlC2)3Na4 contains 3 Al (aluminum), 6 C (carbon) and 4 Na (sodium) atoms.

Input

Contains multiple test cases. For each test case, there will be one line, containing a valid chemical formula. Each line will have no more than 100 characters.

Output

For each line there will be one line of output which is the atomic decomposition of the chemical in the form of a sum as shown in the sample output. The atoms are listed in lexicographical order, and a count of 1 is implied and not explicitly written. There are no blank spaces in the output. All of the counts in the correct output will be representable in 32-bit signed integers.