E. Редактор правильных скобочных последовательностей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Поликарп взялся за разработку текстового редактора правильных скобочных последовательностей (сокращенно ПСП). Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «1» можно получить из нее корректное математическое выражение. Например, последовательности «(())()», «()» и «(()(()))» — правильные, в то время как «)(», «(()» и «(()))(» — нет. Каждая скобка в ПСП имеет парную ей. Например, в «(()(()))»:

  • для 1-й скобки — парная 8-я,
  • для 2-й скобки — парная 3-я,
  • для 3-й скобки — парная 2-я,
  • для 4-й скобки — парная 7-я,
  • для 5-й скобки — парная 6-я,
  • для 6-й скобки — парная 5-я,
  • для 7-й скобки — парная 4-я,
  • для 8-й скобки — парная 1-я.

Редактор Поликарпа пока поддерживает лишь три операции при работе с ПСП. Курсор в редакторе занимает целиком позицию одной из скобок (а не позицию между скобками!). Вот три поддерживаемых операции:

  • «L» — передвинуть курсор влево на одну позицию,
  • «R» — передвинуть курсор вправо на одну позицию,
  • «D» — удалить скобку, в которой находится курсор, парную ей, а также все скобки между ними (то есть удалить подстроку от скобки до парной ей).

После операции «D» курсор перемещается на ближайшую скобку вправо (конечно, среди неудалённых). Если такой нет, то есть был удалён суффикс строки, то на ближайшую скобку влево (конечно, среди неудалённых).

Ниже приведены рисунки нескольких возможных вариантов операции «D».

Всевозможные некорректные операции (сдвиг курсора за границы строки, удаление всей строки) пока Поликарпом не поддержаны.

Поликарп очень гордится своей разработкой, а сможете ли вы реализовать функциональность его редактора?

Входные данные

В первой строке выходных данных следует три целых положительных числа n, m и p (2 ≤ n ≤ 500 000, 1 ≤ m ≤ 500 000, 1 ≤ p ≤ n) — количество скобок в правильной скобочной последовательности, количество операций, а также начальная позиция курсора. Позиции в последовательности нумеруются слева направо, начиная с единицы. Гарантируется, что n чётно.

Далее следует строка из n символов «(» и «)» — правильная скобочная последовательность.

Далее записана строка из m символов «L», «R» и «D» — последовательность операций. Операции выполняются по очереди одна за другой от первой до последней. Гарантируется, что заданные операции никогда не выведут курсор за пределы скобочной последовательности, а также то, что после выполнения всех операций скобочная последовательность останется непустой.

Выходные данные

Выведите правильную скобочную последовательность, полученную в результате выполнения всех операций.

Примеры
Входные данные
8 4 5
(())()()
RDLD
Выходные данные
()
Входные данные
12 5 3
((()())(()))
RRDLD
Выходные данные
(()(()))
Входные данные
8 8 8
(())()()
LLLLLLDD
Выходные данные
()()
Примечание

В первом тестовом примере изначально курсор находится в позиции 5. Рассмотрим действия редактора подробнее:

  1. команда «R» — курсор передвигается вправо в позицию 6;
  2. команда «D» — удаляются скобки с позиции 5 до позиции 6. После этого ПСП принимает вид (())(), курсор находится в позиции 5;
  3. команда «L» — курсор передвигается влево в позицию 4;
  4. команда «D» — удаляются скобки с позиции 1 до позиции 4. После этого ПСП принимает вид (), курсор находится в позиции 1.

Таким образом, ответ равен ().