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. [Image] 

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 ≤ 500 000, 1 ≤ m ≤ 500 000, 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:  command "R" — the cursor moves to the position 6 on the right;  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;  command "L" — the cursor moves to the position 4 on the left;  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 ().

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Spanning trees


Solutions:
def main():
	(n, m, p) = list(map(int, input().split()))
	(xlat, l, s, ll, lr) = ([0] * n, [], input(), list(range(-1, n)), list(range(1, n + 2)))
	p -= 1
	for (i, c) in enumerate(s):
		if c == '(':
			l.append(i)
		else:
			j = l.pop()
			xlat[i] = j
			xlat[j] = i
	for c in input():
		if c == 'D':
			if s[p] == '(':
				p = xlat[p]
			q = ll[xlat[p]]
			p = lr[p]
			(ll[p], lr[q]) = (q, p)
			if p == n:
				p = ll[p]
		else:
			p = (lr if c == 'R' else ll)[p]
	q = p
	while p != -1:
		l.append(s[p])
		p = ll[p]
	l.reverse()
	del l[-1]
	while q != n:
		l.append(s[q])
		q = lr[q]
	print(''.join(l))

def __starting_point():
	main()
__starting_point()


def preproc(str, leng):
	li = []
	res = [-1] * leng
	for i in range(leng):
		if str[i] == '(':
			li.append(i)
		else:
			(start, end) = (li.pop(), i)
			res[start] = end
			res[end] = start
	return res

def delete(flags, cursor, pairs):
	pos = pairs[cursor]
	direction = 1 if pos > cursor else -1
	while pos + direction > 0 and pos + direction < len(flags) and (flags[pos + direction] != -1):
		pos = flags[pos + direction]
	return pos
(leng, op_num, cursor) = map(int, input().strip().split())
cursor = cursor - 1
str = input().strip()
ops = input().strip()
pairs = preproc(str, leng)
flags = [-1] * leng
for i in ops:
	if i == 'R' or i == 'L':
		cursor = {'R': lambda cursor=cursor, flags=flags: cursor + 1 if flags[cursor + 1] == -1 else flags[cursor + 1] + 1, 'L': lambda cursor=cursor, flags=flags: cursor - 1 if flags[cursor - 1] == -1 else flags[cursor - 1] - 1}[i]()
	else:
		delete_to = delete(flags, cursor, pairs)
		delete_from = delete(flags, pairs[cursor], pairs)
		flags[delete_from] = delete_to
		flags[delete_to] = delete_from
		cursor = max(delete_to, delete_from)
		if cursor + 1 < leng and flags[cursor + 1] == -1:
			cursor = cursor + 1
		elif cursor + 1 < leng and flags[cursor + 1] != -1 and (flags[cursor + 1] + 1 < leng):
			cursor = flags[cursor + 1] + 1
		elif min(delete_from, delete_to) - 1 > 0 and flags[min(delete_from, delete_to) - 1] == -1:
			cursor = min(delete_from, delete_to) - 1
		else:
			cursor = flags[min(delete_from, delete_to) - 1] - 1
idx = 0
res = ''
while idx < leng:
	if flags[idx] != -1:
		idx = flags[idx] + 1
		continue
	res += str[idx]
	idx = idx + 1
print(res)


(n, m, p) = list(map(int, input().split()))
(x, v, s, l, r) = ([0] * n, [], input(), list(range(-1, n)), list(range(1, n + 2)))
p -= 1
for (i, c) in enumerate(s):
	if c == '(':
		v.append(i)
	else:
		j = v.pop()
		x[i] = j
		x[j] = i
for c in input():
	if c == 'D':
		if s[p] == '(':
			p = x[p]
		q = l[x[p]]
		p = r[p]
		(l[p], r[q]) = (q, p)
		if p == n:
			p = l[p]
	else:
		p = (r if c == 'R' else l)[p]
q = p
while p != -1:
	v.append(s[p])
	p = l[p]
v.reverse()
del v[-1]
while q != n:
	v.append(s[q])
	q = r[q]
print(''.join(v))


class Node:

	def __init__(self, index):
		self.left = index - 1
		self.right = index + 1
		self.pair = -1
(n, m, p) = map(int, input().split())
brackets = input()
operations = input()
nodes = [Node(i) for i in range(n + 1)]
stack = []
for i in range(n):
	if brackets[i] == '(':
		stack.append(i + 1)
	else:
		pair_id = stack.pop()
		nodes[pair_id].pair = i + 1
		nodes[i + 1].pair = pair_id
for i in range(m):
	if operations[i] == 'L':
		p = nodes[p].left
	elif operations[i] == 'R':
		p = nodes[p].right
	else:
		pair_id = nodes[p].pair
		left = 0
		right = 0
		if p < pair_id:
			left = p
			right = pair_id
		else:
			left = pair_id
			right = p
		left_node = nodes[left].left
		right_node = nodes[right].right
		nodes[left_node].right = right_node
		if right_node != n + 1:
			nodes[right_node].left = left_node
			p = right_node
		else:
			p = left_node
p = nodes[0].right
result = []
while p != n + 1:
	result.append(brackets[p - 1])
	p = nodes[p].right
print(''.join(result))


jump_r = {}
jump_l = {}

def bracket_to_value(bracket):
	if bracket == '(':
		return 1
	if bracket == ')':
		return -1

def move_r(c):
	if c + 1 in jump_r:
		return jump_r[c + 1] + 1
	else:
		return c + 1

def move_l(c):
	if c - 1 in jump_l:
		return jump_l[c - 1] - 1
	else:
		return c - 1

def remove_bracket(s, c, length):
	val = bracket_to_value(s[c])
	initial_c = c
	dir = bracket_to_value(s[c])
	if dir == 1:
		c = move_r(c)
	if dir == -1:
		c = move_l(c)
	val += bracket_to_value(s[c])
	while val != 0:
		if dir == 1:
			c = move_r(c)
		if dir == -1:
			c = move_l(c)
		val += bracket_to_value(s[c])
	final_c = c
	left_end = min(initial_c, final_c)
	right_end = max(initial_c, final_c)
	real_r_end = right_end
	real_l_end = left_end
	jump_r[left_end] = right_end
	jump_l[right_end] = left_end
	if right_end + 1 in jump_r:
		real_r_end = jump_r[right_end + 1]
	if left_end - 1 in jump_l:
		real_l_end = jump_l[left_end - 1]
	jump_l[real_r_end] = real_l_end
	jump_r[real_l_end] = real_r_end
	if real_r_end < length - 1:
		new_c = real_r_end + 1
	else:
		new_c = real_l_end - 1
	return new_c

def smart_print(s):
	i = 0
	while i < n:
		if i not in jump_r:
			print(s[i], end='')
			i += 1
		else:
			i = jump_r[i] + 1

def perform_order(order, s, c, length):
	if order == 'R':
		return move_r(c)
	if order == 'L':
		return move_l(c)
	if order == 'D':
		return remove_bracket(s, c, length)
(n, m, p) = [int(x) for x in input().split()]
p = p - 1
se = input()
orders = input()
for ord in orders:
	p = perform_order(ord, se, p, n)
smart_print(se)


import sys
sys.stderr = sys.stdout
from collections import deque

def brackets(n, m, p, B, S):
	P = [i - 1 for i in range(n + 2)]
	P[0] = None
	Q = [i + 1 for i in range(n + 2)]
	Q[n + 1] = None
	J = [None] * (n + 2)
	D = deque()
	for (i, b) in enumerate(B, 1):
		if b == '(':
			D.append(i)
		elif b == ')':
			j = D.pop()
			J[i] = j
			J[j] = i
	i = p
	for c in S:
		if c == 'L':
			i = P[i]
		elif c == 'R':
			i = Q[i]
		else:
			j = J[i]
			if j < i:
				(i, j) = (j, i)
			Q[P[i]] = Q[j]
			P[Q[j]] = P[i]
			i = Q[j] if Q[j] <= n else P[i]
	L = []
	i = Q[0]
	while i <= n:
		L.append(B[i - 1])
		i = Q[i]
	return L

def main():
	(n, m, p) = readinti()
	B = input()
	S = input()
	print(''.join(brackets(n, m, p, B, S)))

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintt():
	return tuple(readinti())

def readintl():
	return list(readinti())

def readinttl(k):
	return [readintt() for _ in range(k)]

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.__stderr__)
main()


(n, m, p) = [int(x) for x in input().split()]
A = input().rstrip()
B = input().rstrip()
pair = [0] * n
stack = []
for (i, c) in enumerate(A):
	if c == '(':
		stack.append(i)
	else:
		j = stack.pop()
		pair[i] = j
		pair[j] = i
start = 0
pointer = p - 1
left = list(range(-1, n - 1))
right = list(range(1, n + 1))
left[0] = None
right[-1] = None
for c in B:
	if c == 'R':
		pointer = right[pointer]
	elif c == 'L':
		pointer = left[pointer]
	elif pair[pointer] < pointer:
		if right[pointer] is not None:
			left[right[pointer]] = left[pair[pointer]]
		if left[pair[pointer]] is not None:
			right[left[pair[pointer]]] = right[pointer]
		else:
			start = right[pointer]
		if right[pointer] is None:
			pointer = left[pair[pointer]]
		else:
			pointer = right[pointer]
	else:
		if right[pair[pointer]] is not None:
			left[right[pair[pointer]]] = left[pointer]
		if left[pointer] is not None:
			right[left[pointer]] = right[pair[pointer]]
		else:
			start = right[pair[pointer]]
		if right[pair[pointer]] is None:
			pointer = left[pointer]
		else:
			pointer = right[pair[pointer]]
i = start
while right[i] is not None:
	print(A[i], end='')
	i = right[i]
print(A[i])