加密字符串

题解思路

本题的核心在于模拟字符串的编辑过程，涉及字符串的操作、撤销机制和翻转操作。我们可以使用**双端队列（deque）**来高效地完成这些操作。

1. 使用双端队列（deque）存储字符串$t$：
   • R 代表反转字符串，可以使用一个标志位 reversed_flag 来追踪当前字符串是否处于反转状态。
   • Z 代表撤销上一步操作，我们需要记录上一步操作类型，并在遇到 Z 时进行相应撤销。
   • 其他普通字符直接加入 deque，如果当前处于反转状态，则从头部插入，否则从尾部插入。

题目内容

小美有一个由大小写字母混合构成的加密字符串s，你需要按照以下准则将其解密得到字符串$t$。初始时字符串t为空，对于字符串$s$的每一个字符$s_i$:

• 如果$s$的第$i$个字符为‘$R$’(保证至多出现一次)，则反转字符串$t$;
• 如果$s$的第$i$个字符为‘$Z$’(保证至多出现一次)，则撤销上一步操作，具体地:

如果上一步为‘$R$’，则取消反转;

如果上一步为其他字符，删除这个字符；

上一步为空，则跳过这一操作；

• 其他情况，直接将这个字符添加到字符串$t$的结尾;

请你直接输出解密完成后的字符串$t$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≦T≦2×10^5)$代表数据组数，

每组测试数据描述如下:

第一行输入一个长度为$1 ≦len(s)$$≤2×10^5$的字符串$s$代表加密字符串。

除此之外，保证单个测试文件的字符数量之和不超过$10^6$。

输出描述

对于每一组测试数据，新起一行输出解密完成后的字符串$t$。数据保证字符串长度不为$0$。

样例1

输入

2
meRDZ
DameDame

输出

em
DameDame

说明

对于第一组测试数据，解密过程依次为:

• 第一步，将‘$m$’加入，$t$= "$m$";
• 第二步，将‘$e$’加入，$t$="$me$";
• 第三步，翻转字符串，$t$= "$em$";
• 第四步，将‘$D$’加入，$t$="$emD$"
• 第五步，删除第五步加入的字母$t$=“$em$”