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 the 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 = \mathrm{"("} and B_j = \mathrm{")"};
• 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.

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 '')''.

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

Input

The input consists of a string S of N lowercase letters on one line.

Output

Output 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.

Constraints

• 2 \le N \le 10^5

Example 1

Input:

abbaaa

Output:

(()())

Example 2

Input:

abab

Output:

-1