小维塔利喜欢不同的算法。今天他专门为你发明了一种新算法。 Vitaly 的算法适用于由字符“x”和“y”组成的字符串 s,并在运行时使用以下两个操作:
1. 在字符串中找到两个连续的字符,其中第一个等于“y”,第二个等于“x”,然后交换它们。如果有多个合适的字符对,我们会选择距离字符串开头较近的字符对。
2. 在字符串中查找两个连续的字符,其中第一个等于“x”,第二个等于“y”。从字符串中删除这些字符。如果有多个合适的字符对,我们会选择距离字符串开头较近的字符对。
新算法的输入是字符串s,算法的工作原理如下:
1. 如果您可以对字符串应用至少一种所描述的操作,请转至算法的步骤 2。否则,停止执行算法并打印当前字符串。
2. 如果可以应用操作 1,则应用它。否则,应用操作 2。应用操作后,转到算法的步骤 1。
现在,Vitaly 想知道,如果输入接收字符串 s,算法的工作结果将会打印什么。
输入
第一行包含一个非空字符串 s。
保证字符串仅由字符“x”和“y”组成。保证字符串最多包含 106 个字符。保证算法执行的结果不会是空字符串。
输出
如果算法输入的输入接收字符串 s,则在唯一的行中打印作为算法工作结果打印的字符串。
示例
输入 #1
x
输出 #1
x
输入 #2
yxyxy
输出 #2
y
输入 #3
xxxxxy
输出 #3
xxxx
注意
在第一次测试中,算法将在算法的第一步之后结束,因为不可能应用任何操作。因此,字符串不会改变。
在第二个测试中,转换将如下所示:
1.字符串“yxyxy”转换为字符串“xyyxy”;
2. 字符串“xyyxy”转换为字符串“xyxyy”;
3.字符串“xyxyy”转换为字符串“xxyyy”;
4. 字符串“xxyyy”转换为字符串“xyy”;
5. 字符串“xyy”转换为字符串“y”。
结果,我们得到了字符串“y”。
在第三个测试用例中,仅会发生一次转换:字符串“xxxxxy”转换为字符串“xxxx”。因此,答案将是字符串“xxxx”。