Пете в руки попался необычный калькулятор. В нем нет привычных кнопок «+», «-», «*» и «/». Может быть это и к лучшему, ведь кнопки для набора цифр («0», «1», ..., «9») и получения результата («=») расположены на своих местах. Но что самое необычное в этом калькуляторе, так это наличие кнопок «^{}» и «^{}^{}».

После долгих опытов с этим калькулятором, Петя выяснил, что значат эти кнопки.

Кнопка «^{}» означает операцию возведения в степень $$$a^b$$$. Например, если ввести в калькуляторе выражение «2^{}3», то в результате, он выведет число $$$2^3 = 8$$$.

Кнопка «^{}^{}» означает выполнение тетрации $$$\displaystyle {^{b}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}} _{b}$$$. Например, если ввести выражение «2^{}^{}3», то в результате калькулятор выведет число $$$^{3}2 = 2^{2^2} = 16$$$.

Петя планировал вычислить несколько выражений на этом калькуляторе. К сожалению, его опытов хватило, чтобы разобраться с устройством калькулятора, но их также хватило, чтобы привести калькулятор в неработоспособное состояние.

Помогите Пете вычислить значения оставшихся выражений. Для этого необходимо реализовать программу, обрабатывающую выражение с учетом приоритета операций. Тетрация имеет более высокий приоритет (по сравнению с операцией возведения в степень), поэтому такие операции должны быть выполнены в первую очередь. Также нужно учитывать, что вычисление степеней и тетраций необходимо начинать с самых дальних уровней к начальному. Например запись «a^{}^{}b^{}^{}c» должна быть вычислена как $$$^{(^{c}b)}a$$$, а выражение «a^{}b^{}c» — как $$$a^{(b^c)}$$$.