You are given a nonempty bracket sequence s of length n. Find the longest nonempty substring of s that is a regular bracket sequence. Bracket sequences consist of characters '(' and ')'. A bracket sequence is regular if it is either:

• empty
• a concatenation AB of two regular bracket sequences A and B.
• a bracket sequence of the form (A), where A is a regular bracket sequence.

For example, sequences ()(()()) and ((())) are regular while )( and ((((() are not.

Input

A single line contains a single string s.

Output

Print the longest nonempty regular substring or -1 if no such string exists. If there are multiple answers print any.

Constraints

• 1 \leq n \leq 10^5

Example 1

Input:

())(()())(

Output:

(()())

Example 2

Input:

)))(((

Output:

-1