分数: 300 点
问题陈述
你得到了一段密文 S。可以通过以下步骤解密:
- 让 T 是一个空字符串。
- 对于每个 i = 1, 2, \dots, |S| 按此顺序执行以下操作:(|S| 表示长度 S)
- 如果 i- 第一个字符 S is
R,翻转 T; - 如果 i- 第一个字符 S 不是
R,将该字符添加到的末尾 T.
- 如果 i- 第一个字符 S is
- 在上述操作之后,如果有两个连续相同的字符出现 T,移除那两个字符。只要可以进行,就重复此操作。(我们可以证明最终得到的字符串与删除字符的顺序无关。)
打印字符串 T 通过此过程得到。
约束
- S 由小写英文字母和
R. - 1 ≤ |S| ≤ 5 \times 10^5
输入
输入由标准输入按以下格式给出:
S
输出
打印答案。
示例输入 1
ozRnonnoe
示例输出 1
zone
我们可以按如下方式解密它:
- 最初, T 是一个空字符串。
- 添加
o结束时 T,使其o. - 添加
z结束时 T,使其oz. - 反向 T,使其
zo. - 添加
n结束时 T,使其zon. - 添加
o结束时 T,使其zono. - 添加
n结束时 T,使其zonon. - 添加
n结束时 T,使其zononn. - 添加
o结束时 T,使其zononno. - 添加
e结束时 T,使其zononnoe. - 删除两个连续的
n来自 T,使其zonooe. - 删除两个连续的
o来自 T,使其zone.
示例输入 2
hellospaceRhellospace
示例输出 2
答案可能是一个空字符串。