A feature flag stream is a string of the characters (, ), and *. Each * is a wildcard that may be treated as a single (, a single ), or an empty string. Decide whether there is some assignment of the wildcards that makes the whole string a valid balanced parenthesis string.
A string is a valid balanced parenthesis string when it is empty, or it is two valid strings concatenated, or it is ( followed by a valid string followed by ). Equivalently: reading left to right the number of ) never exceeds the number of (, and the totals are equal at the end.
Input format
A single line: the stream (it may be empty). It contains only the characters (, ), and *.
Output format
Print YES if some wildcard assignment yields a valid balanced string, otherwise NO.
Constraints
- 0 <= length of the stream <= 100
- The stream contains only
(,), and*.