Given a chemical formula in the form of string. You need to calculate count of each atoms present in string. 1) The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name. 2) One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow (H2O2 is valid while H1O2 is invalid) 3) Two formulas are concatenated together to produce another formula (H2O2He3Mg4) 4) A formula placed in parentheses, and a count (optionally added) is also a formula ((H2O2)3). Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
Input Format
A string (chemical formula) Ex: K4(ON(SO3)2)2
Output Format
A string (atom with count) Ex: K4N2O14S4
Constraints
1 <= formula.length <= 1000
formula consists of English letters, digits, '(', and ')'.
formula is always valid.
All the values in the output will fit in a 32-bit integer.
Notice
NA
Example
Input
Mg(OH)2
Output
H2MgO2