Сервал попрощался с детским садом Джапари и начал свою школьную жизнь в школе Джапари.

На его любимом уроке математики учитель рассказал ему следующие интересные определения.

Скобочной последовательностью называется строка, состоящая только из символов «(», «)».

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

Обозначим за $$$|s|$$$ длину строки $$$s$$$. Собственным префиксом $$$s[1\dots l]$$$ $$$(1\leq l< |s|)$$$ строки $$$s = s_1s_2\dots s_{|s|}$$$ назовем строку $$$s_1s_2\dots s_l$$$. Обратите внимание, что пустая строка и вся строка не являются собственными префиксами по определению.

Изучив эти определения, он придумал новую задачу. Он выписал строку $$$s$$$, состоящую только из символов «(», «)», «?». Теперь он хочет заменить каждый из «?» в $$$s$$$ независимо на один из символов «(» или «)», чтобы все собственные префиксы строки не являлись правильной скобочной последовательностью, а сама строка являлась.

В конце концов Сервал всего лишь ученик начальной школы, поэтому эта задача для него слишком трудная. Как его лучший друг, может быть, вы поможете ему заменить знаки вопроса? Если существует несколько решений, вы можете найти любое.