eolymp
bolt
Try our new interface for solving problems
Problems

Bracket sequence

Bracket sequence

Time limit 4 seconds
Memory limit 128 MiB

The bracket sequence is a correct arithmetic expression from which all numbers and operation signs have been removed. For example,

1 + ( ( ( 2 + 3 ) + 5 ) + ( 3 + 4 ) ) → ( ( ( ) ) ( ) )

Input data

A sequence of opening and closing brackets is given. The length of the sequence is no more than 4 \cdot 10^6.

Output data

Print "YES" if the bracket sequence is correct and "NO" otherwise.

Examples

Input example #1
((())())
Output example #1
YES
Input example #2
(()
Output example #2
NO