You are given a string consisting only of the characters (, ), [, ], {, and }.

A string is considered balanced if:

• Every opening bracket is closed by the same type of bracket.
• Brackets are closed in the correct order.

Determine whether the given string is balanced.

Input

A single line containing the string ~s~.

Output

Print YES if ~s~ is balanced, otherwise print NO.

Constraints

• ~1 \le |s| \le 2 \cdot 10^5~
• ~s~ contains only (, ), [, ], {, }

Example 1

Input

()[]{}

Output

YES

Example 2

Input

([{}])

Output

YES

Example 3

Input

([)]

Output

NO