Valid Parenthesis String

Given a string s containing only the characters '(', ')' and '*', determine if the string can be considered valid.

A string is valid if it satisfies the following conditions:

• Every left parenthesis ( has a corresponding right parenthesis ).
• Every right parenthesis ) has a corresponding left parenthesis (.
• Left parenthesis ( appears before the corresponding right parenthesis ).
• The character * can be treated as a single left parenthesis (, a single right parenthesis ), or an empty string.

You may express the above conditions in mathematical terms as follows:

• If we let low and high denote the possible minimum and maximum number of unclosed left parentheses while processing the string, then for each character c in s:

For c = (:
\( low = low + 1 \) and \( high = high + 1 \)

For c = ):
\( low = max(low - 1, 0) \) and \( high = high - 1 \)

For c = *:
\( low = max(low - 1, 0) \) and \( high = high + 1 \)

The string is valid if after processing all characters, \( low = 0 \) and during processing \( high \) never becomes negative.

inputFormat

The input consists of a single line containing the string s.

Note: The string will only contain the characters '(', ')' and '*'.

outputFormat

Output a single line: True if the string is valid according to the rules above, otherwise False.

## sample

()

True