Valid Parentheses

Problem

Given a string containing only the characters (, ), {, }, [, and ], determine whether the bracket structure is valid. A structure is valid if:

Every opening bracket has a corresponding closing bracket of the same type.
Brackets are closed in the correct order (proper nesting).
No closing bracket appears without a matching opening bracket.

Input Format

A single line containing the bracket string s.

Output Format

Print valid if the bracket structure is valid, invalid otherwise.

Examples

Example 1

Input(A single line containing the bracket string s.)

{[()]}

Output

valid

All brackets are properly nested and matched.

Example 2

Input(A single line containing the bracket string s.)

{[(])}

Output

invalid

The ')' at position 3 does not match '[' at the top of the stack.

Constraints

•0 <= len(s) <= 10000
•s consists only of characters '(', ')', '{', '}', '[', ']'

Execution limits: 2s · 256MB

Loading interactive editor…