Valid Parentheses Checker

You are given a string S consisting solely of the characters ('), {'}, and [']. Your task is to determine whether the input string has valid parentheses.

A string is considered valid if:

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

Formally, a string S is valid if it satisfies the following condition:

$$ S \text{ is valid if and only if every opening bracket } x \text{ has a corresponding closing bracket } y \text{ such that the brackets are properly nested.} $$

For example, the string "()[]{}" is valid, whereas "(]" or "([)]" are not.

inputFormat

The input consists of a single line containing a non-negative length string S which includes only the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Output a single line: True if the input string has valid parentheses, otherwise False.

## sample

()

True