Hide

Problem D
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

Please log in to submit a solution to this problem

Log in