eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Вирази

Вирази

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z - w) - арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w - * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

Для вычисления выражения, заданного в постфиксной нотации, используется алгоритм, работающий со стеком. Стек - это структура данных, поддерживающая две операции:

  1. push: число кладется на верх стека.

  2. pop: число снимается с вершины стека.

Во время вычисления выражение обрабатывается слева направо. Если приходит число, то кладем его на стек. Если приходит оператор, то извлекаем два числа из стека, применяем к ним оператор и результат кладем обратно в стек. Следующий псевдокод обрабатывает оператор O:

a := pop();

b := pop();

push(b O a);

Результатом выражения будет единственное число, оставшееся в стеке.

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push и pop, но их смысл немного другой:

  1. push: число вставляется в конец очереди.

  2. pop: из начала очереди извлекается число.

Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?

Вхідні дані

Первое число содержит число t (t200). Каждая из следующих t строк содержит одно выражение в постфиксной записи. Арифметические операции представляются заглавными буквами, числа представляются прописными буквами. Длина каждого выражения менее 10000 символов.

Вихідні дані

Для каждой входной строки выведите выражение, результат которого будет таким же, если использовать в алгоритме очередь вместо стека. Чтобы результат определялся однозначно, считайте, что заданные операторы не являются ассоциативными или коммутативными.

Приклад

Вхідні дані #1
2
xyPzwIM
abcABdefgCDEF
Вихідні дані #1
wzyxIPM
gfCecbDdAaEBF
Джерело University of Ulm Local Contest 2007.07.06