Balanced Brackets

Lab Python Intermediate 20 points

Read a line and print balanced if every (), [], {} is properly opened and closed, otherwise unbalanced. Ignore other characters.

Input

One line.

Output

One word.

Example

Input

{[()()]}

Output

balanced

Sample input available Sample output available

Editor

Python

Hints

Push opening brackets on a stack.

A closing bracket must match the top of the stack.

Solution explanation

A stack naturally matches the most recent unclosed bracket.

Show solution

pairs = {")": "(", "]": "[", "}": "{"}
stack = []
ok = True
for ch in input():
    if ch in "([{":
        stack.append(ch)
    elif ch in pairs:
        if not stack or stack.pop() != pairs[ch]:
            ok = False
            break
print("balanced" if ok and not stack else "unbalanced")

Output

Answer