Welcome to The Mirror of Galadriel, one of the activities that will follow in the The Fellowship of Code. If you haven't been here before, this is a place where programming problems of different types will be proposed to be solved as fast as possible.

Without further ado, we leave you with the next problem.

Good luck adventurers!

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Constraints

• 1 <= s.length <= 10^4
• s consists of parentheses only '()[]{}'.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Run, you fools! No extra spicy stuff this time.