Balanced Brackets Checker

Given a string containing various characters including brackets, determine if the sequence of brackets is balanced. The string may include letters, digits, punctuation, and other symbols, but only the brackets ('(', ')', '[', ']', '{', '}') need to be checked.

A bracket sequence is considered balanced if every opening bracket has a corresponding closing bracket in the correct order. More formally, the condition can be expressed as:

\(\text{For every opening bracket, there exists a corresponding closing bracket such that the substring between them is also balanced.}\)

For example, the string "a(b[c]d){e}f" is balanced while "a(b[c)d]{e}f" is not.

inputFormat

The input consists of a single line containing the string to be checked. The string may contain spaces and any printable characters.

Input is given via stdin.

outputFormat

Output a single line: print "Balanced" if the brackets in the input string are balanced, otherwise print "Not Balanced". The output should be written to stdout.

a(b[c]d){e}f

Balanced