Маленький Виталик любит разные алгоритмы. Сегодня он изобрел новый алгоритм специально для Вас. Алгоритм Виталика работает со строкой s, состоящей из символов «x» и «y», и в процессе выполнения использует две следующие операции:
- Найти в строке два подряд идущих символа таких, что первый из них равен «y», а второй «x» и поменять их местами. Если имеется несколько подходящих пар символов, выбирается пара символов, которая находится ближе к началу строки.
- Найти в строке два подряд идущих символа таких, что первый из них равен «x», а второй «y» и удалить их из строки. Если имеется несколько подходящих пар символов, выбирается пара символов, которая находится ближе к началу строки.
Входными данными для нового алгоритма является строка s, а сам алгоритм работает следующим образом:
- Если к строке можно применить хотя бы одну из описанных операций, перейти к шагу 2 алгоритма. Иначе закончить выполнение алгоритма, и вывести текущую строку.
- Если можно применить операцию 1, то применить операцию 1. Иначе применить операцию 2. После применения операции перейти к шагу 1 алгоритма.
Теперь Виталику интересно, что будет выведено в результате работы алгоритма, если на вход алгоритма подается строка s.
Выходные данные
В единственную строку выведите строку, которая будет выведена в результате работы алгоритма, если на вход алгоритма подается строка s.
Примечание
В первом тесте алгоритм закончится после прохождения первого пункта, так как никакую операцию применить нельзя. Таким образом строка не изменится.
Во втором тесте ход преобразований будет таким:
- строка «yxyxy» превращается в строку «xyyxy»;
- строка «xyyxy» превращается в строку «xyxyy»;
- строка «xyxyy» превращается в строку «xxyyy»;
- строка «xxyyy» превращается в строку «xyy»;
- строка «xyy» превращается в строку «y».
В результате будет выведена строка «y».
В третьем тесте произойдет только одно преобразование: строка «xxxxxy» превращается в строку «xxxx». Таким образом ответом будет строка «xxxx».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
x
|
x
|
|
2
|
yxyxy
|
y
|
|
3
|
xxxxxy
|
xxxx
|