괄호 짝 맞추기

올바른 괄호 문자열을 다음과 같이 정의한다.

• 빈 문자열은 올바른 괄호 문자열이다.
• $B$가 올바른 괄호 문자열이면 $(B)$도 올바른 괄호 문자열이다.
• $L$과 $R$가 모두 올바른 괄호 문자열이면 둘을 이어 붙인 $LR$도 올바른 괄호 문자열이다.

길이가 $N$인 올바른 괄호 문자열 $B$의 $i$번째 문자를 $B_i$라고 하자. 두 인덱스 $i$와 $j$ ($1 \le i < j \le N$)가 다음 두 조건을 모두 만족하면 $B_i$와 $B_j$는 서로 짝이다.

• $B_i$는 ( 이고 $B_j$는 ) 이다.
• $j = i + 1$이거나, 부분 문자열 $B_{i+1} B_{i+2} \dots B_{j-1}$이 올바른 괄호 문자열이다.

소문자로 이루어진 문자열 $S$의 $i$번째 문자를 $S_i$라고 하자. 올바른 괄호 문자열 $B$가 $S$에 대응한다는 것은 다음 두 조건이 성립한다는 뜻이다.

• $B$의 길이는 $S$의 길이와 같다.
• $i < j$인 모든 인덱스 쌍에서 $B_i$와 $B_j$가 짝이면 $S_i = S_j$이다.

소문자 $N$개로 이루어진 문자열 $S$가 주어진다. $S$에 대응하는 올바른 괄호 문자열 중 사전순으로 가장 앞서는 것을 구한다.

첫째 줄에 소문자 $N$개로 이루어진 문자열 $S$가 주어진다.

• $2 \le N \le 100000$
• 괄호 문자열 $A$가 괄호 문자열 $B$보다 사전순으로 앞선다는 것은, 어떤 인덱스 $i$ ($1 \le i \le N$)가 있어서 $j < i$인 모든 $j$에 대해 $A_j = B_j$이고 $A_i < B_i$인 경우를 말한다.
• 문자 (는 문자 )보다 사전순으로 앞선다.

첫째 줄에 $S$에 대응하는 올바른 괄호 문자열 중 사전순으로 가장 앞서는 문자열을 출력한다. 그런 문자열이 없으면 -1을 출력한다.