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