最近,Polycarp 开始开发一种文本编辑器,该编辑器仅适用于正确的括号序列(缩写为 CBS)。
请注意,如果可以通过添加“+”-s 和“1”-s 来获得正确的数学表达式,则括号序列是正确的。例如,序列“(())()”、“()”和“(()(()))”是正确的,而“)(”、“(()”和“(()))(”则不正确。CBS中的每个括号都有一对。例如,在“(()(()))”中:
- 第一个支架与第八个支架配对,
- 2d 支架与 3d 配对,
- 3d 支架与 2d 配对,
- 第 4 个支架与第 7 个支架配对,
- 第 5 个支架与第 6 个支架配对,
- 第 6 个支架与第 5 个支架配对,
- 第 7 个支架与第 4 个支架配对,
- 第 8 个支架与第 1 个支架配对。
Polycarp的编辑器目前在CBS使用过程中仅支持三种操作。编辑器中的光标占据其中一个括号的整个位置(而不是括号之间的位置!)。支持三种操作:
- «L» — 将光标向左移动一位,
- «R» — 将光标向右移动一位,
- «D» — 删除光标所在括号,删除与其配对的括号以及它们之间的所有括号(即删除光标所在括号与其配对括号之间的子字符串)。
操作“D”后光标移动到右侧最近的括号(当然,在非删除的中间)。如果没有这样的括号(即CBS的后缀被删除),则光标移动到左侧最近的括号(当然,在未删除的中间)。
下面有图片说明了操作“D”的几种用法。
Polycarp 的编辑器不支持所有错误操作(将光标移到 CBS 末尾、删除整个 CBS 等)。
Polycarp 对他的开发感到非常自豪,你能实现他的编辑器的功能吗?
输入
第一行包含三个正整数 n、m 和 p (2 ≤ n ≤ 500 000, 1 ≤ m ≤ 500 000, 1 ≤ p ≤ n)——正确括号序列中括号的个数、运算次数和光标的初始位置。序列中的位置从左到右从 1 开始编号。保证n是偶数。
后面是 n 个字符的字符串“(”和“)”,形成正确的括号序列。
然后跟随 m 个字符的字符串“L”、“R”和“D”——一系列操作。操作从第一个到最后一个依次进行。保证给定的操作永远不会将光标移动到括号序列之外,并且在所有操作之后括号序列将是非空的。
输出
打印正确的括号序列,该序列是对初始序列应用所有操作的结果。
示例
输入 #1
8 4 5 (())()() RDLD
输出 #1
()
输入 #2
12 5 3 ((()())(())) RRDLD
输出 #2
(()(()))
输入 #3
8 8 8 (())()() LLLLLLDD
输出 #3
()()
注意
在第一个示例中,光标最初位于位置 5。考虑编辑器的操作:
1.命令“R”——光标移动到右侧位置6;
2、命令“D”——从位置5到位置6删除括号。此时CBS的形式为(())(),光标位于位置5;
3.命令“L”——光标移动到左侧位置4;
4.命令“D”——从位置1到位置4删除括号。此时CBS采用()形式,光标位于位置1。
因此,答案等于()。