Valid Parenthesis String With Wildcards

s contains (, ) and *. Each * can be a (, a ) or an empty string. Return True if the stars can be chosen so that the brackets are valid (every ( closed by a later ), never closing more than was opened).

For "(*)" and "(*))" the answer is True; for ")(" it is False.

Examples

Example 1

Input:

check_valid_string('(*)')

Output:

True

Example 2

Input:

check_valid_string('(*))')

Output:

True

Example 3

Input:

check_valid_string(')(')

Output:

False

Constraints

• 0 <= len(s) <= 200000
• Characters are (, ) and *.