Background

This week's lab exercise focuses on a classic computer science problem: bracket matching. We will start with the fundamental balancing check and add a layer of complexity with hierarchical nesting rules, which are often found in mathematical and programming contexts. This exercise is an excellent application of the stack data structure.

Description

You are given a string representing a mathematical formula. Your task is to determine if all bracket characters—(), [], and {}—are both balanced and correctly nested according to a specific hierarchy.

For the string to be considered valid, it must satisfy two conditions:

1. Balanced Brackets: Every opening bracket must have a corresponding closing bracket of the same type. For example, [()] is balanced, but [(]) and (() are not.
2. Nesting Hierarchy: The brackets must adhere to a strict nesting order, reflecting common mathematical notation.
   • Curly braces {} are the outermost-level brackets. They can contain square brackets, and parentheses.
   • Square brackets [] are the middle-level brackets. They can only contain parentheses.
   • Parentheses () are the innermost-level brackets. They can only contain other parentheses.

Therefore, an expression like { [ ( ) ] }, [ ] is valid. However, if a parenthesis contains a square bracket (i.e., ( [ ] )), or a square bracket contains a curly brace (i.e. [ {} ]), the nesting is invalid.

Your program should process the input string and output a single boolean flag: true if both conditions are met for all brackets in the string, and false otherwise.

Important: Non-bracket characters in the string should be ignored when checking for balance and nesting.

Format

Input

Two lines:

1. An integer $n$ ($1 \leq n \leq 10^5$), the length of the string.
2. A line containing a string $s$ ($1 \leq |s| \leq 10^5$). The string can contain alphanumeric characters (a-z, A-Z, 0-9), mathematical operators (+, -, *, /), and the six bracket characters: (, ), [, ], {, }.

Output

Output a single word on a single line: true or false.

Samples

Sample 1

15
{a+[b*(c-d)]-e}

true

Explanation: The brackets are { [ ( ) ] }. This is perfectly balanced and follows the nesting hierarchy.

Sample 2

9
(a+[b*c])

false

Explanation: A parenthesis () contains a square bracket []. This violates the nesting hierarchy.

Sample 3

13
[a*{b/(c-d)}]

false

Explanation: A square bracket [] contains a curly brace {}. This violates the nesting hierarchy.

Sample 4

9
a+b-(c*d]

false

Explanation: The opening parenthesis ( is closed by a square bracket ]. The brackets are not balanced.

Sample 5

15
100 * 200 + 300

true

Explanation: There are no brackets in the string, so the conditions are vacuously met.

Hint

Online interactive guide

Limitation

1s, 128MiB for each test case.