#P18127. Spin & Rotate!
Spin & Rotate!
Spin & Rotate!
有一个大正方形 ,顶点按逆时针顺序给出。每个顶点处都有一根固定绳索的钉子。有两条很长的绳子:一条连接顶点 ,另一条连接顶点 。绳子的长度可以任意伸缩,但不能离开正方形上方的区域。
初始时两条绳子没有缠绕:如果把两条绳子都缩短,那么其中一条可以落在正方形的一条边上,另一条落在相对边上。
机器人 Ka-BAN 有两种操作:
-
S(spin):把四个绳端从钉子上取下,保持绳子之间的全部缠绕关系,绕竖直轴逆时针旋转 ,再固定到新的钉子上。这等价于正方形和绳子不动,而把顶点名称顺时针旋转:
- 的新名称是 ;
- 的新名称是 ;
- 的新名称是 ;
- 的新名称是 。
-
R(rotate):从顶点 上取下绳端并交换后再固定。交换时,原来固定在 的绳端从原来固定在 的绳端上方越过。若从边 外侧观察,相当于两个绳端绕彼此逆时针旋转 。
给定 Ka-BAN 从左到右执行的一串 S、R 操作。你需要为拥有同样两种操作的机器人 Iz-BAN 编写一个最短程序,使执行后两条绳子重新变得没有缠绕。
可以证明答案一定存在且唯一。如果绳子已经无缠绕,输出单个字符 S。
输入格式
第一行包含测试用例数 ,满足 。
接下来 行,每行包含一个只由 S、R 组成、长度为 的字符串,表示 Ka-BAN 执行的程序,满足
所有字符串长度之和不超过 。
输出格式
对于每组数据,输出一行只含 S、R 的最短解缠程序。
样例 1
14
R
S
RR
SR
RS
SS
RRR
SRR
RSR
SSR
RRS
SRS
RSS
SSS
SR
S
SRSRR
S
R
S
SRSRRSRR
S
S
SR
RSRR
S
SR
S
样例 2
5
SRRSRRSRR
SRRRSRRR
RRRSRRRSRRR
SRRSRRSRRSRRSRRSRRSRRSRRSRRSR
SRRRSRRRSRRRSRRRSRRRSRRRSRRRS
SRSRRR
SRSRRSRR
SRSRRSRRRSRRRSRR
SRRRRRRRRR
RSRRSRRRSRRRSRRRSRRRSRRRSRR