Valid Parentheses

You are given a string S consisting only of the six characters: '(', ')', '{', '}', '[' and ']'. Your task is to determine whether the input string is a valid sequence of parentheses. A valid string satisfies the following conditions:

• Every opening parenthesis has a corresponding closing parenthesis of the same type.
• Opening parentheses must be closed in the correct order.

In other words, if we define the matching pairs as \( ( , ) \), \( \{ , \} \), and \( [ , ] \), then for each opening parenthesis in the string, there must be a later closing parenthesis that matches it, and paired parentheses must be properly nested.

For example, the string "{[()]}" is valid, while "{[(])}" is not.

inputFormat

The input is provided via stdin and consists of a single line containing the string S. The string may be empty. Do not output any prompt.

outputFormat

Output to stdout a single line: YES if the string is a valid parentheses sequence, or NO otherwise.

{[()]}

YES