G. AmShZ выиграл пари
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Прямо перед Евро-2020 AmShZ и Safar сделали ставки на то, кто станет чемпионом, AmShZ поставил на Италию, а Safar — на Францию.

Конечно же, AmShZ выиграл. Следовательно, Safar дал ему скобочную последовательность $$$S$$$. Обратите внимание, что скобочная последовательность — это строка, состоящая из символов '(' и ')'.

AmShZ может выполнить следующую операцию любое количество раз:

  • Сначала, он разрезает свою строку $$$S$$$ на три (возможно, пустых) последовательных подстроки $$$A, B$$$ и $$$C$$$. Затем он склеивает их с помощью символов '(' и ')', в результате чего получается новая строка $$$S$$$ = $$$A$$$ + '(' + $$$B$$$ + ')' + $$$C$$$.

    Например, если $$$S$$$ = «))(» и AmShZ разрежет ее на $$$A$$$ = «», $$$B$$$ = «))» и $$$C$$$ = «(», то в качестве новой строки он получит $$$S$$$ = «()))(».

После выполнения некоторых (возможно, ни одной) операций, AmShZ отдает свою строку Кеши и просит его найти исходную строку. Конечно, Кеши может найти более одной возможной начальной строки. Кеши заинтересован в нахождении лексикографически наименьшей возможной начальной строки.

Ваша задача — помочь Кеши в достижении его цели.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$a$$$ является префиксом $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ отличаются, строка $$$a$$$ имеет букву, которая появляется раньше в алфавите, чем соответствующая буква в $$$b$$$.
Входные данные

Единственная строка ввода содержит единственную строку $$$S$$$ — строку после операций $$$(1\le |S|\le 3 \cdot 10^5)$$$.

Гарантируется, что первый символ $$$S$$$ — ')'.

Выходные данные

Выведите лексикографически наименьшую возможную начальную строку перед операциями.

Пример
Входные данные
)(()(())))
Выходные данные
)((())))
Примечание

В первом примере можно преобразовать «)((())))» в «)(()(())))», разбив её на «)(», пустую строку, и «(())))». Можно показать, что это лексикографически наименьшая возможная начальная строка