Valid Parentheses Checker

Given a string s containing only the characters (', ')', '{', '}', '[' and ']', determine if the input string is valid.

A string is considered valid if:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets are closed in the correct order.

This condition can be expressed in LaTeX as follows: $$ s \text{ is valid if } \forall i, \; \text{if } s[i] \text{ is an opening bracket, then there exists a } j>i \text{ such that } s[j] \text{ is the corresponding closing bracket, and the substring } s[i+1:j-1] \text{ is also valid.} $$

Your task is to determine whether the given input string is valid. The program should read an input string from stdin and output True if it is valid, or False otherwise, to stdout.

inputFormat

The input consists of a single line containing the string s which only includes the characters (', ')', '{', '}', '[' and ']'. The length of s is at least 0 and at most 10⁴ characters.

outputFormat

Output a single line: True if the input string is valid, and False otherwise.

()

True