Valid Parentheses Checker

The challenge is to determine whether a string consisting solely of the characters (' , ')', '[' , ']', '{' , '}' is valid. A string is considered valid if:

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

One common approach is to use a stack data structure. For example, whenever an opening bracket is encountered, push it onto the stack, and when a closing bracket is encountered, check if the top of the stack contains the matching opening bracket. In mathematical notation, if stack initially is empty, then after processing the string, the condition for validity can be summarized as:

$$\text{valid} \iff \text{stack} = []$$

Consider examples:

• Input: () gives output VALID.
• Input: ()[]{{}} gives output VALID.
• Input: (} gives output INVALID.
• Input: ([)] gives output INVALID.

inputFormat

The input consists of a single line containing a non-empty string composed only of the characters '(', ')', '[', ']', '{', '}'.

outputFormat

The output is a single line containing either VALID if the string is a valid parentheses sequence, or INVALID otherwise.

## sample

()

VALID

</p>