A string of brackets is balanced when every opening bracket is closed by the same type of bracket in the correct order. Bracket types: (), [], {}.
Input
One line of up to 10^5 bracket characters.
Output
BALANCED or NOT BALANCED.
Hint
Push opening brackets on a stack; on a closing bracket, the top of the stack must be its matching opener.
Read from standard input and write to standard output. 5 test cases in total (3 hidden). Tests for this language run inside your browser.