Задача . G. AmShZ выиграл пари

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