Bracket Match

A valid bracket sequence is defined as follows.

• The empty string is a valid bracket sequence.
• If $B$ is a valid bracket sequence, then $(B)$ is a valid bracket sequence.
• If $L$ and $R$ are both valid bracket sequences, then their concatenation $LR$ is a valid bracket sequence.

Let $B$ be a valid bracket sequence of length $N$, and let $B_i$ be its $i$-th character. Two indices $i$ and $j$ with $1 \le i < j \le N$ are matching brackets when both of these hold.

• $B_i$ is ( and $B_j$ is ).
• $j = i + 1$, or the substring $B_{i+1} B_{i+2} \dots B_{j-1}$ is a valid bracket sequence.

Let $S$ be a string of lowercase letters, and let $S_i$ be its $i$-th character. A valid bracket sequence $B$ matches $S$ when both of these hold.

• $B$ has the same length as $S$.
• For every pair of indices $i < j$, if $B_i$ and $B_j$ are matching brackets, then $S_i = S_j$.

You are given a string $S$ of $N$ lowercase letters. Find the lexicographically smallest valid bracket sequence that matches $S$.

The first line contains a string $S$ of $N$ lowercase letters.

• $2 \le N \le 100000$
• A bracket sequence $A$ is lexicographically smaller than a bracket sequence $B$ if there is an index $i$ ($1 \le i \le N$) such that $A_j = B_j$ for every $j < i$ and $A_i < B_i$.
• The character ( is lexicographically smaller than the character ).

Print the lexicographically smallest valid bracket sequence that matches $S$. If no such sequence exists, print -1.