Valid Parentheses Checker

You are given a string that may contain various characters including the parentheses ('). Your task is to determine if the order of the parentheses in the string is valid. A string is considered to have valid parentheses if:

• Every opening parenthesis ( has a corresponding closing parenthesis ).
• The parentheses close in the correct order.

This condition can be formally described as: for a sequence of characters, define a counter that is incremented by 1 for every ( and decremented by 1 for every ). Then, the sequence is valid if

\(\text{For every prefix, } count \ge 0 \quad \text{and} \quad count = 0 \text{ at the end.}\)

Note that you should ignore any characters other than '(' and ')'.

inputFormat

The input consists of a single line containing a string s. The string may include any printable characters.

Input Format:

s

outputFormat

Output a single line: True if the ordering of the parentheses in the string is valid, and False otherwise.

Output Format:

True | False

## sample

()

True