另类蛋糕制造 (ACM) 有 n 名员工。他们现在正在就一些非常重要的问题进行投票,世界主要媒体正在试图预测投票结果。
每位员工都属于两个派系之一:民主党派或共和党派,这两个派系对投票结果持有相反的意见。投票程序比较复杂:
1. n 名员工每人发表一份声明。他们从员工 1 开始,到员工 n 结束,一一做出陈述。如果到了第 i 个员工发表声明的时刻,他不再有投票权,他就跳过轮到他(并且不再参与本次投票)。
2. 当员工发表声明时,他不能采取任何行动,也不能声明其他员工之一不再有投票权。可以拒绝投票已经发表声明或等待发表声明的人。如果有人被拒绝投票,他直到最后都不再参与投票。
3. 当所有员工都完成发言后,重复该过程:再次,从 1 开始到 n 结束仍有资格投票的每个员工都进行发言。
4. 重复该过程,直到只剩下一名有资格投票的员工,并由他决定整个投票的结果。当然,他会投票支持适合他的部分的决定。
您知道员工将投票的顺序以及他们的最佳行为(并且他们还知道顺序以及谁属于哪个部分)。预测投票结果。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 员工数量。
下一行包含 n 个字符。如果第 i 个雇员来自民主党派,则第 i 个字符为“D”;如果他来自共和党,则第 i 个字符为“R”。
输出
如果投票结果适合共和党人,则打印“D”;如果共和党获胜,则打印“R”。
示例
输入 #1
5 DDRRR
输出 #1
D
输入 #2
6 DDRRRR
输出 #2
R
注意
考虑第一个样本的投票场景之一:
1. 员工 1 拒绝员工 5 投票。
2. 员工 2 拒绝员工 3 投票。
3. 员工 3 无投票权并跳过轮到他(他被员工 2 拒绝)。
4. 员工 4 拒绝员工 2 投票。
5. 员工 5 无投票权并跳过轮到他(他被员工 1 拒绝)。
6. 员工 1 否认员工 4。
7. 现在只有员工 1 有投票权,因此投票以共和党人获胜而结束。