Problem A
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\leq n\leq 100\, 000)$ — 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.
Sample Input 1  Sample Output 1 

6 ([]{}) 
Valid 
Sample Input 2  Sample Output 2 

8 (())((() 
Invalid 
Sample Input 3  Sample Output 3 

6 ([}{]) 
Invalid 