解题思路

核心结论：设字符串中字符 L 的数量为 $cntL$，那么答案一定是：

也就是说：

题目内容

笨蛋同学设计了一条长度为 $n$的走廊，位置编号为$1,2,…,n$。每个位置上都有一个指示牌，指向左边或右边，分别用字符 L 与 R 表示。

现在有一个小球放在某个起点位置 $s$。小球运动规则如下：

• 记当前位置为 $p$。若位置 $p$的指示牌为 L，则小球会向左走；若为 R，则小球会向右走。
• 小球会沿着该方向一直走，直到遇到第一个 “此前从未到达过” 的位置（初始时，起点$s$ 即视为已被到达），然后停在该位置继续按该位置的指示牌规则运动。换句话说，当前轮只看出发点的指示牌，沿途忽略，直到第一个未访问位置才停。

小球会一直运动，直到它从走廊左侧走出（到达位置 $0$）或从走廊右侧走出（到达位置 $n+1$）。我们分别称其最终从左侧出界为 L，从右侧出界为 R。

对于每一个起点 $s=1,2,…,n$，请你输出小球最终会从哪一侧出界。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T$（$1≤T≤2×10^5$），代表数据组数。

每组测试数据描述如下：

• 第一行输入一个整数 $n$（$1≤n≤2×10^5$）。
• 第二行输入一个长度为 $n$ 的字符串$w$，只包含字符 L 与 R，其中 $w_i$ 表示位置 $i$的指示牌方向。

除此之外，保证单个测试文件中所有测试数据的$n$ 之和不超过$2×10^5$。

输出描述

对于每组测试数据，输出一行长度为$n$ 的字符串。第$i$个字符表示起点为$i$时小球的出界方向：从左侧出界输出 L，从右侧出界输出 R。

样例1

输入

2
5
LRRLL
3
LLL

输出

LLLRR
LLL