Detective Conan Shinichi needs your help! His friend, Dr. Ai Haibara has narrowed down a chemical formula in order to reverse the effects of APTX 4869, the drug that made Shinichi turn into a child. However, the formula of the new drug is a long one, and Ai Haibara needs to make sure that she doesn't accidentally murder you, or else who is going to solve that murder mystery if the main detective is dead? Detective Shinichi and Ai Haibara now asks for your help to determine the exact number of each atom in the formula.

Here are the characteristics of the formula:

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

~1~ or more digits representing the count of that element may follow if the count is greater than one. If the count is ~1~, no digits follow. For example, H2O and H2O2 are possible, but H1O2 is impossible (because there is only one hydrogen atom, and thus it shouldn't have any digits following it).

A formula placed in parentheses, and a count (optionally added) is also a formula. For example, (H2O2) and (H2O3)3 are formulas. When this happens, the outside count is distributed among the inside of the parentheses, so (H2O3)3 will turn into H6O9.

Input Specification

One line, a string ~S~, the formula of the new drug.

Output Specification

Given the formula, output the count of all the elements in the following form: For each element, you should output the first name, followed by its count (if that count is more than ~1~). The elements need to be sorted in lexicographical order in terms of name, and the output should be on one line.

Constraints

• All atom names consist of lowercase letters, except for the first character which is uppercase.
• ~1 \le |S| \le 5 \times 10^3~
• The formula will only consist of letters, digits, round parentheses, and is a valid formula as defined in the problem.
• Any digits, that come after an element or parentheses, will be in the range ~[1, 1000]~.

Sample Input 1

H2O

Sample Output 1

H2O

Explanation for Sample Output 1

There are ~2~ hydrogen atoms and ~1~ oxygen atom.

Sample Input 2

Mg(OH)2

Sample Output 2

H2MgO2

Explanation for Sample Output 2

After applying the parentheses, the formula string would be this: MgO2H2.

There are ~1~ magnesium atom, ~2~ oxygen atoms and ~2~ hydrogen atoms.

Sample Input 3

K4(ON(SO3)2)2

Sample Output 3

K4N2O14S4

Explanation for Sample Output 3

After applying the first set of parentheses, we have K4O2N2(SO3)4. Then applying the second set of parentheses, we have K4O2N2S4O12. Then by adding up the common atoms, we get K4O14N2S4.

There are ~4~ potassium atoms, ~14~ oxygen atoms, ~2~ nitrogen atoms, and ~4~ sulfur atoms.