Balanced Parentheses with Wildcards

You are given a string s consisting of parentheses ('(', ')'), square brackets ('[' ,']'), curly braces ('{', '}') and the wildcard character *. The * character can be treated as an empty character or as any one of the parentheses/brackets/braces. Your task is to determine if the string can be balanced by replacing each * with a valid empty character or a matching bracket.

Formally, a string s is balanced if:

• Every opening bracket has a corresponding closing bracket.
• The brackets are closed in the correct order.
• The wildcard * can be replaced by an empty string or by any bracket needed to make the string balanced.

You may assume that matching pairs are: \( (\) with \( ) \), \( [ \) with \( ] \), and \( { \) with \( } \).

Examples:

• Input: (*)) → Output: True
• Input: (() → Output: False
• Input: [(*){*}] → Output: True

inputFormat

The input consists of a single line containing the string s. The string may contain any of the characters: '(', ')', '[', ']', '{', '}', and '*'.

Read the input from standard input (stdin).

outputFormat

Output a single line: True if the string can be balanced, or False otherwise. Write your answer to standard output (stdout).

## sample

(*))

True