Remove Invalid Parentheses

Given a string s containing English letters and parentheses ('(') 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 correctly matched. Return all possible results in lexicographical order.

You must remove the minimum number of parentheses so that the resulting string is valid. For example, given s = "()())()", the valid outputs are (())() and ()()().

Note: When counting removals, only parentheses are subject to removal. Other characters should remain in their original order.

The problem can be interpreted mathematically as minimizing the number of removals k such that there exists a subset of indices whose removal leads to a valid sequence. In particular, if you let \( \mathcal{S} \) denote the set of all valid sequences derived from s, then the task is to find all y \( \in \mathcal{S} \) generated by removing exactly k characters, where k is minimized.

inputFormat

The input consists of a single line containing a string s. The string may include lowercase and uppercase English letters, digits, and the characters '(' and ')'.

Input Format:

{s}

outputFormat

Output all valid strings in lexicographical order, each on a new line. If the result is an empty string (i.e. valid output is a list containing an empty string), output an empty line.

Output Format:

result_string_1
result_string_2
... 
result_string_n

## sample

()())()

(())()
()()()

</p>