Valid Parentheses Replacement

You are given a string s consisting of the characters (, ) and ?. Your task is to determine whether it is possible to replace every ? with either ( or ) such that the resulting string is a valid parentheses sequence.

A valid parentheses sequence satisfies the following conditions:

• The total number of opening parentheses is equal to the total number of closing parentheses.
• At any prefix of the sequence, the number of closing parentheses does not exceed the number of opening parentheses.

This problem can be formally represented using the following condition involving cumulative counts: Let min_open and max_open be the minimum and maximum possible number of unmatched opening parentheses, respectively, after processing the string. Then, the sequence is valid if and only if \[ \min_{open} = 0 \quad \text{and} \quad \max_{open} \ge 0 \text{ at all times.} \]

Read the input from stdin and print the result to stdout as either True or False.

inputFormat

The input consists of a single line containing the string s that only includes the characters (, ), and ?.

Constraints:

• 1 ≤ |s| ≤ 10⁴

outputFormat

Output a single line: True if the string can be transformed into a valid parentheses sequence by replacing all ? characters, otherwise False.

## sample

(()?)

True