Count the Atoms

A chemical formula lists elements, each written as an uppercase letter that may be followed by lowercase letters (H, Mg, Cl), with an optional count after it: H2O has two H atoms and one O atom. A group in brackets can have a count too, which multiplies everything inside it: Mg(OH)2 has one Mg, two O and two H. Groups can be nested, and square brackets work exactly like round ones.

Write count_atoms(formula) that returns a string listing every element in alphabetical order, each followed by its total count, leaving the count out when it is 1.

Examples

count_atoms("H2O")            # returns 'H2O'
count_atoms("Mg(OH)2")        # returns 'H2MgO2'
count_atoms("K4[ON(SO3)2]2")  # returns 'K4N2O14S4'

In K4[ON(SO3)2]2, the round group holds 2 S and 6 O, so the square group holds 7 O, 1 N and 2 S, and its count of 2 doubles all of that.

Constraints

• formula has 1 to 1,000 characters and is always valid, with matching brackets.
• Counts are whole numbers from 1 to 10,000 without leading zeros.

Note

Element names are compared as plain strings, so C comes before Ca, and Ca before Cl.