Lexicographically Smallest Matching Parentheses Sequence

You are given a string \(s\) consisting of lowercase letters. Your task is to construct a valid parentheses sequence \(p\) (consisting only of '(' and ')') of the same length as \(s\) such that \(s\) and \(p\) match and \(p\) is the lexicographically smallest among all valid sequences satisfying this condition.

The matching between \(s\) and \(p\) is defined as follows:

• The lengths of \(s\) and \(p\) must be equal.
• If in the valid parentheses sequence \(p\) a left parenthesis at position \(i\) matches a right parenthesis at position \(j\) (according to the usual matching rules), then it must hold that \(s_i = s_j\).

A valid parentheses sequence is defined recursively as:

[ \text{Valid} = "" \quad\text{or}\quad (A)B \quad\text{where}\quad A \text{ and } B \text{ are valid parentheses sequences.} ]

If no valid parentheses sequence exists, output -1.

Note: In lexicographical order, the character '(' is considered smaller than ')'.

inputFormat

The input consists of a single line containing a non-empty string \(s\) of lowercase letters.

outputFormat

If a valid parentheses sequence exists that matches \(s\) as described, print the lexicographically smallest such sequence. Otherwise, output -1.

sample

abba

(())