Valid Parenthesis String

You are given a string s consisting of only the characters '(', ')' and '*'. The task is to determine whether the string is valid. A string is considered valid if the '*' characters can be replaced by either '(', ')' or an empty string such that the resulting string forms a proper parenthesis sequence.

A proper parenthesis sequence meets the following criteria:

• Every left parenthesis '(' has a corresponding right parenthesis ')'.
• The matching must follow the correct order; a ')' cannot appear before its matching '('.

This condition can be formally written in LaTeX as:

$$\text{For } s = s_1 s_2 \dots s_n \text{ where } s_i \in \{ '(', ')', '*' \}, $$$$\exists\; f: \{i\,|\,s_i = '*'\} \to \{'(', ')', ''\}\text{ such that the string } s' \text{ obtained by replacing each } s_i = '*' \text{ with } f(i) \text{ is a valid parenthesis sequence.} $$

inputFormat

The input is provided via stdin as a single line containing the string s.

outputFormat

Output to stdout either True if the string is valid according to the above rules; otherwise output False.

## sample

(*))

True