Question

Verifying a Corrupted Log Sequence

A logging system records opening and closing markers for nested operations, but due to a transmission error, some characters in the log were corrupted and replaced with a wildcard symbol.

You are given a string S consisting only of the characters '(', ')', and '*'. Each '*' could originally have been either '(', ')', or an empty string (i.e., it may be treated as not present at all).

Determine whether there exists some way to resolve every '*' such that the resulting string of parentheses is validly balanced (every opening bracket has a matching closing bracket later, in properly nested order).

Input

A single line containing the string KaTeX can only parse string typed expression.

Output

Print KaTeX can only parse string typed expression if some valid resolution exists, otherwise print KaTeX can only parse string typed expression.

Example

Example 1:
Input

(*))

Output

YES

Explanation
Resolving the KaTeX can only parse string typed expression as KaTeX can only parse string typed expression gives the string KaTeX can only parse string typed expression, which is validly balanced: the first and fourth characters form a matching pair, and the second and third characters form a matching pair nested inside.

Example 2:
Input

Output

NO

Explanation
A single unmatched opening bracket with no wildcards to resolve it can never be balanced.

Example 3:
Input

Output

YES

Explanation
A single wildcard can simply be resolved as an empty string, leaving a valid (empty) balanced sequence.

Online

Explore Newton School

Recent Questions

Most Solved Questions

Least Solved Questions