Перебирая изобретения великого учёного Д. И. Менделеева, Вы перенеслись в другую вселенную и стали его учеником. Но в один день, когда Менделеев отдыхал под яблоней, от порыва ветра на него свалилось пару яблок, после чего великий учёный забыл, как раскрывать скобки в химических формулах.
В его записях вы вычитали, что в этом мире существуют всего 26 элементов, обозначаются они заглавными буквами латинского алфавита, сами же формулы строятся по следующему принципу:
Формула — последовательность латинских букв, разделённых числами, которые обозначают количество элемента, стоящего перед числом; если же числа нет, то количество элемента равно единице. Пример: H4ZO2 эквивалентно H4O2Z1.
Также в формуле могут стоять скобки, которые показывают, что количество элементов внутри скобок должно быть умножено на число после скобок. Так, H2(O2Z)3 — это то же самое, что и H2O6Z3.
Напишите программу, которая поможет Менделееву раскрывать скобки в химических формулах.
Формат входных данных
На ввод подаётся строка, состоящая из латинских символов, скобок и цифр. Строка всегда является правильной формулой.
Формат выходных данных
Выведите строку, содержащую правильно раскрытую формулу из ввода. Символы должны выписываться в отсортированном относительно алфавита виде. После каждой буквы обязательно выводится число, обозначающее количество соответствующего элемента.
Подсказка: для обработки вложенных скобок удобно использовать стек.
| № | Входные данные | Выходные данные |
|
1
|
Z3(O(N2O3)2)3
|
N12O21Z3
|
|
2
|
N(OY3)2
|
N1O2Y6
|
|
3
|
H4ZO2
|
H4O2Z1
|