Valid Parentheses Checker

You are given a string consisting only of the characters (' and ')'. Your task is to determine whether the string is a valid sequence of nested parentheses. A valid sequence satisfies the following conditions:

• Every opening parenthesis ( has a corresponding closing parenthesis ).
• Parentheses are properly nested. That is, for any prefix of the string, the number of ( is at least the number of ).

Mathematically, you can define a counter balance where for every character in the string, you add 1 for ( and subtract 1 for ). The sequence is valid if and only if the balance never becomes negative during the traversal and is zero at the end. In LaTeX, the condition can be expressed as:

$$\text{Valid if } \forall k, \; \sum_{i=1}^{k} a_i \ge 0 \text{ and } \sum_{i=1}^{n} a_i = 0, \quad a_i = \begin{cases}1,& \text{if } s_i = '(';\\ -1,& \text{if } s_i = ')'.\end{cases} $$

This problem is common in compiler design and parsing.

inputFormat

The input consists of a single line containing a string s composed only of the characters (' and ')'. The string may be empty.

outputFormat

Output a single line: True if the string is a valid parentheses sequence, otherwise False.

## sample

()

True

</p>