Codeforces Global Round 17 |
---|
Закончено |
Прямо перед Евро-2020 AmShZ и Safar сделали ставки на то, кто станет чемпионом, AmShZ поставил на Италию, а Safar — на Францию.
Конечно же, AmShZ выиграл. Следовательно, Safar дал ему скобочную последовательность $$$S$$$. Обратите внимание, что скобочная последовательность — это строка, состоящая из символов '(' и ')'.
AmShZ может выполнить следующую операцию любое количество раз:
Например, если $$$S$$$ = «))(» и AmShZ разрежет ее на $$$A$$$ = «», $$$B$$$ = «))» и $$$C$$$ = «(», то в качестве новой строки он получит $$$S$$$ = «()))(».
После выполнения некоторых (возможно, ни одной) операций, AmShZ отдает свою строку Кеши и просит его найти исходную строку. Конечно, Кеши может найти более одной возможной начальной строки. Кеши заинтересован в нахождении лексикографически наименьшей возможной начальной строки.
Ваша задача — помочь Кеши в достижении его цели.
Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:
Единственная строка ввода содержит единственную строку $$$S$$$ — строку после операций $$$(1\le |S|\le 3 \cdot 10^5)$$$.
Гарантируется, что первый символ $$$S$$$ — ')'.
Выведите лексикографически наименьшую возможную начальную строку перед операциями.
)(()(())))
)((())))
В первом примере можно преобразовать «)((())))» в «)(()(())))», разбив её на «)(», пустую строку, и «(())))». Можно показать, что это лексикографически наименьшая возможная начальная строка
Название |
---|