Valid Bracket Sequence

You are given a string s containing only the characters '(', ')', '{', '}', '[' and ']'. Your task is to determine whether the input string is a valid bracket sequence.

A bracket sequence is considered valid if all of the following conditions are met:

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

You may refer to the conditions using the following formula in \( \LaTeX \) format: \( S = \{ s \mid s = \varepsilon \text{ or } s = (s') \text{ or } s = \{s'\} \text{ or } s = [s'] \text{ with } s' \in S \} \).

Read the input from stdin and output the result to stdout. The output should be VALID if the string is a valid bracket sequence, and INVALID otherwise.

inputFormat

The input consists of a single line containing the string s which represents the bracket sequence.

Note: The string may be empty.

outputFormat

Print a single line to stdout that is either VALID or INVALID depending on whether the bracket sequence is valid or not.

## sample

{[()]}

VALID

</p>