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

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов.

Задана правильная скобочная последовательность $$$s$$$ и целое число $$$k$$$. Ваша задача — найти такую правильную скобочную последовательность длины ровно $$$k$$$, что она является подпоследовательностью $$$s$$$.

Гарантируется, что такая последовательность всегда существует.