Balanced Parentheses Checker

You are given a string s containing alphanumeric characters and parentheses (i.e. '(', ')', '[', ']', '{', '}'). Your task is to determine whether the sequence of parentheses in the string is "balanced". A string is considered balanced if:

• Every opening bracket has a corresponding closing bracket of the same type.
• The brackets are closed in the correct order.

More formally, if we denote the string by s and use a last-in-first-out (LIFO) structure (i.e. a stack), then when scanning from left to right:

For every prefix of s, if we let S be the sequence of unmatched opening brackets, all closing brackets should correspond to the most recent unmatched opening bracket. In mathematical notation, if we define the condition using \(\text{stack}\) operations, then at the end we require that
\(\text{stack} = \emptyset\).

Output balanced if the parentheses in the string are balanced and not balanced otherwise.

inputFormat

The input consists of a single line containing the string s which may include alphanumeric characters and the characters '(', ')', '[', ']', '{', '}'.

Note: The input is read from standard input (stdin).

outputFormat

Output a single line: either balanced if the string has properly matched and nested parentheses, or not balanced otherwise.

Note: The output should be printed on standard output (stdout).

## sample

a(b)c[d]{e}

balanced