531. Chemistry Assessment

0

Hard

Nobita needs help with his chemistry assessment. He has been given a chemical formula in the form of a string and he wants to count the number of each atom present. However, his usual helper, Doraemon, is unavailable as he is on a date with Mii-Chan. So, Nobita is seeking assistance from you to ensure he doesn't score zero on his assessment. The chemical formula follows certain rules: an atomic element always starts with an uppercase character, followed by zero or more lowercase letters to represent the name. It may be followed by one or more digits to indicate the count of that element, with no digits following if the count is 1. For example, "H2O" and "H2O2" are valid formulas, but "H1O2" is not. Formulas can be concatenated together to create another formula. For example, "H2O2He3Mg4" is a valid formula. Formulas can also be enclosed in parentheses, with an optional count added. For example, "(H2O2)" and "(H2O2)3" are valid formulas. Your task is to print the count of all elements as a string in the following format: the first name (in sorted order), followed by its count (if the count is more than 1), followed by the second name (in sorted order), followed by its count (if the count is more than 1), and so on. The test cases have been designed such that all the values in the output will fit in a 32-bit integer.

Input Format

The input consists of a single line containing a string.

Output Format

The output should be a string.

Example

Input

H2O

Output

H2O

Constraints

1 <= string.length <= 1000
string consists of English letters, digits, '(', and ')'.
string is always valid.
Loading...

View Submissions

Console