We define a valid bracket sequence as a string that is either:

• The empty string;
• A string (B), where B is a valid bracket sequence.
• LR, the concatenation of two strings L and R which are both valid bracket sequences.

Let $B$ be a valid bracket sequence of length $N$. We define $B_i$ to be the $i$-th character of sequence $B$. For two indices $i$ and $j$, $1\le i<j\le N$, we say that $B_i$ and $B_j$ are matching brackets if:

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

Let $S$ be a string of lowercase English letters. We define $S_i$ to be the $i$-th character of string $S$. We say that a valid bracket sequence $B$ matches $S$ if:

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

For a given string $S$ consisting of $N$ lowercase letters, find the lexicographically smallest valid bracket sequence that matches $S$, or print -1 if no such bracket sequence exists.

Input

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

Output

In the output you should write either a string $B$ with $N$ characters that represents the lexicographically smallest bracket sequence that matches the input string, or -1 if no such bracket sequence exists.

Notes and constraints

• $2\le N\le 100000$
• For test cases worth $10$ points $N\le 18$.
• For test cases worth another $27$ points $N\le 2000$.
• We say that 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 each $j<i$, and $A_i<B_i$.
• Character ( is considered lexicographically smaller than character ).

Sample Input 1

abbaaa

Sample Output 1

(()())

Note for Sample Input 1

Another valid bracket sequence is (())(), but this is not the smallest lexicographic solution.

Sample Input 2

abab

Sample Output 2

-1

Note for Sample Input 2

There is no valid bracket sequence that matches the given string.