638. Number of Atoms

Given a chemical formula with element names (an uppercase letter optionally followed by lowercase letters), optional counts, and nested parentheses with multipliers, return the count of each element as a string, listing elements in alphabetical order with counts greater than 1 appended (counts of 1 omitted). The input is JSON {formula}.

Input: JSON {formula}.

Output: String — the element counts in alphabetical order.

Examples

Input: {"formula":"H2O"}
Output: H2O
Explanation: Two hydrogens, one oxygen.

Input: {"formula":"Mg(OH)2"}
Output: H2MgO2
Explanation: Multiplier applies inside parentheses.

Input: {"formula":"K4(ON(SO3)2)2"}
Output: K4N2O14S4
Explanation: Nested multipliers.

Constraints

• 1<=|formula|<=1000
• valid formula

Asked by