Balanced Parentheses Checker

You are given a string s consisting exclusively of the characters ( and ). The task is to determine whether the sequence of parentheses is valid, meaning that the parentheses are balanced and properly nested. In other words, every opening parenthesis ( must have a corresponding closing parenthesis ) in the correct order.

A sequence is considered valid if:

• Every ( has a matching ).
• At no point should a closing parenthesis ) appear without a corresponding unmatched opening parenthesis (.

This can be formally represented using LaTeX as:

$$\text{A sequence } s \text{ is valid if } \forall i, \; \#(\text{ up to } i) \geq \#)(\text{ up to } i) \text{ and } \#(s)=\#)(s). $$

Your program should read the input string from stdin and output either True or False to stdout depending on whether the sequence is valid or not.

inputFormat

The input consists of a single line containing a string s (with no spaces) that represents a sequence of parentheses.

outputFormat

Print True if the sequence of parentheses is valid. Otherwise, print False.

## sample

()

True