Олимпиадный тренинг

Задача . E. Редактор правильных скобочных последовательностей


Задача

Темы: снм Строки Структуры данных *1700

Недавно Поликарп взялся за разработку текстового редактора правильных скобочных последовательностей (сокращенно ПСП). Напомним, что скобочная последовательность называется правильной, если путем вставки в нее символов «+» и «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» — последовательность операций. Операции выполняются по очереди одна за другой от первой до последней. Гарантируется, что заданные операции никогда не выведут курсор за пределы скобочной последовательности, а также то, что после выполнения всех операций скобочная последовательность останется непустой.

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

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

Примечание

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

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

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


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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет