Valid Parentheses

Riverbend School writes its timetables in a template language where every section is wrapped in brackets, and a template that is not properly closed silently drops half the week. The checker in the editor has to say yes or no before the file is saved. Three kinds of bracket are in use, they can sit inside one another, and a section closed with the wrong kind is just as broken as one never closed at all.

Task: Print whether the template's brackets are properly closed.

Input

A single line holding up to 1000 characters, each one of (, ), [, ], {, }. The line may be empty.

Output

One line holding exactly Valid or exactly Invalid. Brackets are valid when every closing bracket matches the most recently opened bracket that is still open, and nothing is left open at the end. An empty line is valid.

Example:

Input:
{[()]}

Output:
Valid