Wildcard Bracket Balance

You are given a string s made of the characters '(', ')', and '*'.

Each '*' may independently be replaced by a '(', by a ')', or by nothing at all. Return true if some choice of replacements turns s into a balanced bracket string, and false otherwise.

A bracket string is balanced when every '(' has a matching ')' after it and every ')' has a matching '(' before it.

Examples

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "(*)"
Output: true
Explanation: Treat the '*' as nothing, leaving "()".

Example 3

Input: s = "(*))"
Output: true
Explanation: Treat the '*' as a '(' , giving "(())".