Valid Parentheses

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

A string is considered valid if all the following conditions are met:

• Every opening bracket has a corresponding closing bracket.
• Opening brackets must be closed in the correct order.

More formally, a string is valid if for every prefix of the string, the number of closing brackets does not exceed the number of opening brackets, and the following condition holds in LaTeX:

\( \forall i,\; \text{if } s_i \text{ is an opening bracket then there exists } j > i \text{ such that } s_i \text{ matches } s_j \).

For example:

• () is valid.
• ()[]{} is valid.
• (] is not valid.
• {[()]} is valid.
• {[}] is not valid.

inputFormat

The input consists of a single line string s which contains only the characters '(' , ')' , '{' , '}' , '[' and ']'.

outputFormat

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

## sample

()

True