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