Скобочной последовательностью называется строка, состоящая только из символов «(» и «)». Правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.
Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.
Задана правильная скобочная последовательность $$$s$$$ и целое число $$$k$$$. Ваша задача — найти такую правильную скобочную последовательность длины ровно $$$k$$$, что она является подпоследовательностью $$$s$$$.
Гарантируется, что такая последовательность всегда существует.
В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$n$$$ и $$$k$$$ четные) — длина $$$s$$$ и длина последовательности, которую требуется найти.
Во второй строке содержится строка $$$s$$$ — правильная скобочная последовательность длины $$$n$$$.
Выведите единственную строку — правильную скобочную последовательность длины ровно $$$k$$$, что она является подпоследовательностью $$$s$$$.
Гарантируется, что такая последовательность всегда существует.
6 4
()(())
()()
8 8
(()(()))
(()(()))
Название |
---|