Valid Parentheses String with Wildcards

You are given a string s consisting of three types of characters: (', ), and wildcard characters (any character that is not (' or )). The wildcard characters can be converted into either (', ), or be removed (i.e. an empty string). Determine whether it is possible to transform the string into a valid parentheses string.

A parentheses string is considered valid if every opening parenthesis (' has a corresponding closing parenthesis ) and the pairs are correctly nested. Mathematically, after processing the string from left to right, if we define two running counters low and high that track the minimum and maximum possible number of unmatched (' respectively, then the string is valid if and only if:

• For every prefix, high \ge 0 (i.e. we never need more (' than we have), and
• At the end, low = 0 (i.e. the number of unmatched (' is 0).

The update rules for each character are as follows:

• If the character is (': then low += 1 and high += 1.
• If the character is ): then low = max(low - 1, 0) and high -= 1.
• If the character is a wildcard: then low = max(low - 1, 0) and high += 1 (since it can be treated as an extra (' or removed).

If at any point high < 0, the string cannot be valid. Finally, if low == 0 after processing the entire string, then a valid transformation exists.

Your task is to implement a program that reads the input string from standard input and prints True if the string can be transformed into a valid parentheses string, and False otherwise.

inputFormat

The input consists of a single line containing the string s composed of characters (', ), and any other wildcard characters.

outputFormat

Output a single line: True if the string can be transformed into a valid parentheses string, otherwise False.

## sample

()

True

</p>