Problem H
Bracket Matching

Given a bracket sequence $s$ of length $n$, you are to determine if it is valid!

A valid bracket sequence is defined recursively as:

• “”

• $(x)$ where $x$ is a valid bracket sequence

• $[x]$ where $x$ is a valid bracket sequence

• $\{x\}$ where $x$ is a valid bracket sequence

• $xy$, where $x$ and $y$ are valid bracket sequences

Input

The first line of each contains one integer $n$ $(2\le n\le 100000)$ — the length of the bracket sequence.

The second line of each test case contains a string $s$ — the bracket sequence in the question. It is guaranteed that $s$ only contains $()[]\{\}$ as characters.

Output

Output Valid if the sequence is a valid bracket sequence, otherwise output Invalid.

6
([]{})

Valid

8
(())((()

Invalid

6
([}{])

Invalid