Прямо перед Евро-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$$$.