ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4747: Correct Bracket Sequence Editor 正确的括号序列编辑器

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：5 通过：5
提交提交记录统计Web Board

题目描述

Polycarp有一个长度为 n 的括号串。

我们设 prei 为字符串中第 11 位到第 i 位的左括号数量减去右括号数量，那么当每个 1⩽i⩽n ， prei⩾0 。同时 pren=0 时，我们认为这个括号串合法。

现在Polycarp为合法括号串设计了一种编辑器，这个编辑器支持如下操作:

  1. L，将光标左移一格
  2. R，将光标右移一格
  3. D，删除这个括号到与它对应的括号之间的所有字符，在删除之后，光标会跳到它右边的没有被删除的最左边的括号处，如果没有这样的括号了，那么光标会跳到它左边的没有被删除的最右边的括号处。

举个例子:


上图中，在第一排左边的串使用D，使得 [2,3][2,3] 全部被删掉了。

第二排中，使用D，删除了 [4,7][4,7] ，因为第 77 个括号的配对括号在 44 处。

第三排也是一样。

Polycarp的编辑器不支持错误的操作，例如删掉整个字符串。

Polycarp对他的设计感到自豪，但是他不会实现这个编辑器，所以他想请你来帮他实现，你能帮他实现编辑器的功能吗？

Recently Polycarp started to develop a text editor that works only with correct bracket sequences (abbreviated as CBS).
Note that a bracket sequence is correct if it is possible to get a correct mathematical expression by adding "+"-s and "1"-s to it. For example, sequences "(())()", "()" and "(()(()))" are correct, while ")(", "(()" and "(()))(" are not. Each bracket in CBS has a pair. For example, in "(()(()))":
  • 1st bracket is paired with 8th,
  • 2d bracket is paired with 3d,
  • 3d bracket is paired with 2d,
  • 4th bracket is paired with 7th,
  • 5th bracket is paired with 6th,
  • 6th bracket is paired with 5th,
  • 7th bracket is paired with 4th,
  • 8th bracket is paired with 1st.
Polycarp's editor currently supports only three operations during the use of CBS. The cursor in the editor takes the whole position of one of the brackets (not the position between the brackets!). There are three operations being supported:
  • «L»− move the cursor one position to the left,
  • «R»− move the cursor one position to the right,
  • «D»− delete the bracket in which the cursor is located, delete the bracket it's paired to and all brackets between them (that is, delete a substring between the bracket in which the cursor is located and the one it's paired to).
After the operation "D" the cursor moves to the nearest bracket to the right (of course, among the non-deleted). If there is no such bracket (that is, the suffix of the CBS was deleted), then the cursor moves to the nearest bracket to the left (of course, among the non-deleted).
There are pictures illustrated several usages of operation "D" below.
All incorrect operations (shift cursor over the end of CBS, delete the whole CBS, etc.) are not supported by Polycarp's editor.
Polycarp is very proud of his development, can you implement the functionality of his editor?
Input
The first line contains three positive integers n, m and p (2≤n≤500000, 1≤m≤500000, 1≤p≤n)− the number of brackets in the correct bracket sequence, the number of operations and the initial position of cursor. Positions in the sequence are numbered from left to right, starting from one. It is guaranteed that n is even.
It is followed by the string of n characters "(" and ")" forming the correct bracket sequence.
Then follow a string of m characters "L", "R" and "D"− a sequence of the operations. Operations are carried out one by one from the first to the last. It is guaranteed that the given operations never move the cursor outside the bracket sequence, as well as the fact that after all operations a bracket sequence will be non-empty.
Output
Print the correct bracket sequence, obtained as a result of applying all operations to the initial sequence.
Examples
Input 
8 4 5
(())()()
RDLD
Output 
()
Input 
12 5 3
((()())(()))
RRDLD
Output 
(()(()))
Input 
8 8 8
(())()()
LLLLLLDD
Output 
()()
Note
In the first sample the cursor is initially at position 5. Consider actions of the editor:
  1. command "R"− the cursor moves to the position 6 on the right;
  2. command "D"− the deletion of brackets from the position 5 to the position 6. After that CBS takes the form (())(), the cursor is at the position 5;
  3. command "L"− the cursor moves to the position 4 on the left;
  4. command "D"− the deletion of brackets from the position 1 to the position 4. After that CBS takes the form (), the cursor is at the position 1.
Thus, the answer is equal to ().

输入格式

输入共三行。

第一行，三个整数 n,m,p ，分别表示括号串长度，操作数量和光标的初始位置。

第二行，一个长度为 n 的括号串。

第三行，一个长度为 m 的字符串，表示操作序列。

输出格式

输出共一行。

第一行，一个括号串。表示原括号串进行了 �m 个操作过后的括号串。



输入样例 复制 

12 5 3
((()())(()))
RRDLD

输出样例 复制 

(()(()))

数据范围与提示

1⩽p⩽n⩽5×105,1⩽m⩽5×105
在第一个示例中，光标最初位于位置 5。考虑编辑器的操作：
  1. 命令 “R”− 光标移动到右侧位置 6;
  2. 命令“D”−删除从位置5到位置6的括号。之后 CBS 采用 （（））（） 的形式，光标位于位置 5;
  3. 命令“L”−光标移动到左侧位置4;
  4. 命令“D”−删除从位置1到位置4的括号。之后 CBS 采用 （） 的形式，光标位于位置 1。
因此，答案等于 （）。

分类标签