bracketex

Problem Description

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

A valid bracket sequence is defined recursively as:

  • "" or
  • (x) where x is a valid bracket sequence, or
  • xy, where x and y are valid bracket sequences.

However, two other pairs of brackets can be found in the bracket sequence, '[' which is to be matched with ']' and '{' which is to be matched with '}'.

Limits

For all tests: each character will be one of the following: '(', ')', '[', ']', '{', '}'.

Subtask 1 (10%): 1 ≤ L ≤ 4.

Subtask 2 (30%): 1 ≤ L ≤ 1000.

Subtask 3 (20%): 1 ≤ L ≤ 100000. However, each character will be either '(' or ')'.

Subtask 4 (40%): 1 ≤ L ≤ 100000.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain one integer, L.

The second line of input will contain one string, the bracket sequence.

Output

The output should contain one string, either "Valid" or "Invalid".

Sample Testcase 1

Input

6
([]{})

Output

Valid

Sample Testcase 2

Input

8
(())((()

Output

Invalid

Sample Testcase 3

Input

6
([}{])

Output

Invalid

Submitting .cpp to 'bracketex'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 128MB
No. of ACs: 190
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 10
2 30
3 20
4 40
5 0