Valid Bracket Sequence

You are given a string consisting solely of the characters ('), {'} and [']. Your task is to determine whether the bracket sequence is valid or not.

A bracket sequence is considered valid if:

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

In mathematical terms, a sequence S is valid if and only if after processing all characters using a stack (i.e., pushing opening brackets and matching closing brackets appropriately) the stack is empty. This can be summarized by the formula:

$$\text{Valid}(S) \Longleftrightarrow \text{stack}(S)=\emptyset $$

For example, the sequence ([]) is valid while the sequence {[(])} is not.

inputFormat

Input is a single line string representing the bracket sequence. The string may be empty and will only contain the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Output a single line to stdout: print "Valid" if the sequence is balanced, otherwise print "Invalid".## sample

([])

Valid

</p>