Remove Invalid Parentheses

Given a string s consisting of lowercase English letters and the characters '(' and ')', remove the minimum number of invalid parentheses in order to make the input string valid. A string is considered valid if the parentheses are properly balanced.

For example, given s = "(a)())()", the possible valid strings are: (a())() and (a)()().

The output should list all valid strings in lexicographical order, each on a new line.

inputFormat

The input consists of a single line containing the string s. This string consists only of lowercase letters, '(' and ')'.

outputFormat

Print each valid string on a new line, in lexicographical order.## sample

(a)())()

(a())()
(a)()()