Correct Bracket Sequence Editor
### 题目描述 `Polycarp`有一个长度为 $n$ 的括号串。 我们设 $pre_i$ 为字符串中第 $1$ 位到第 $i$ 位的左括号数量减去右括号数量，那么当每个 $1\leqslant i\leqslant n$ ， $pre_i\geqslant0$ 。同时 $pre_n=0$ 时，我们认为这个括号串合法。 现在`Polycarp`为合法括号串设计了一种编辑器，这个编辑器支持如下操作: 1. `L`，将光标左移一格 2. `R`，将光标右移一格 3. `D`，删除这个括号到与它对应的括号之间的所有字符，在删除之后，光标会跳到它右边的没有被删除的最左边的括号处，如果没有这样的括号了，那么光标会跳到它左边的没有被删除的最右边的括号处。 举个例子: !(https://cdn.luogu.com.cn/upload/vjudge_pic/CF670E/08b0f9032003921a97680a954e716fd13a3de759.png) 上图中，在第一排左边的串使用`D`，使得 $[2,3]$ 全部被删掉了。 第二排中，使用`D`，删除了 $[4,7]$ ，因为第 $7$ 个括号的配对括号在 $4$ 处。 第三排也是一样。 `Polycarp`的编辑器不支持错误的操作，例如删掉整个字符串。 `Polycarp`对他的设计感到自豪，但是他不会实现这个编辑器，所以他想请你来帮他实现，你能帮他实现编辑器的功能吗？ ### 输入格式 输入共三行。 第一行，三个整数 $n,m,p$ ，分别表示括号串长度，操作数量和光标的初始位置。 第二行，一个长度为 $n$ 的括号串。 第三行，一个长度为 $m$ 的字符串，表示操作序列。 ### 输出格式 输出共一行。 第一行，一个括号串。表示原括号串进行了 $m$ 个操作过后的括号串。 ### 数据范围 $1\leqslant p\leqslant n\leqslant 5\times 10^5,1\leqslant m\leqslant 5\times 10^5$
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. !(https://cdn.luogu.com.cn/upload/vjudge_pic/CF670E/08b0f9032003921a97680a954e716fd13a3de759.png)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?
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.
Print the correct bracket sequence, obtained as a result of applying all operations to the initial sequence.
8 4 5 (())()() RDLD
12 5 3 ((()())(())) RRDLD
8 8 8 (())()() LLLLLLDD
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 ().