Description

You are given a string $s$ consisting of lowercase letters. You need to construct a lexicographically smallest (assume the left parenthesis is lexicographically smaller than the right parenthesis) valid parenthesis sequence that matches this string.

A string and a parenthesis sequence are defined to match as follows: first, their lengths must be equal; second, for every pair of matched left and right parentheses at positions $i,j$, it must hold that $s_i=s_j$.

If there is no solution, output -1.

Input Format

One line containing a string $s$.

Output Format

One line containing a parenthesis sequence, or -1.

abbaaa

(()())

Hint

For $100\%$ of the testdata, $2\le n\le 10^5$.

Translated by ChatGPT 5