Chemistry

The chemical formula of a molecule M tells us which elements it is made of. A formula follows this 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 multiplies the subgroup S that immediately precedes it.

For example, H2O consists of two H (hydrogen) atoms and one O (oxygen) atom. Likewise, (AlC2)3Na4 consists of 3 Al (aluminium), 6 C (carbon), and 4 Na (sodium) atoms.

Given a chemical formula, write a program that determines which elements make it up.

The input consists of several test cases. Each test case is a single line containing one valid chemical formula, and each line is at most 100 characters long. Input continues until end of file (EOF).

For each test case, print the elements that make up the given formula on one line. Sort the elements in dictionary (lexicographic) order of their symbols, and print each element as its count immediately followed by its symbol, joining consecutive elements with '+'. If an element's count is 1, omit the count.