Practice Coding with the exercise "Brackets, extreme edition."

1864

Statement

Goal

You must determine whether a given expression has valid brackets. This means all the parentheses (), square brackets [] and curly brackets {} must be correctly paired & nested.

The expression does not contain whitespace characters.

Input

A single line: expression.

Output

A single line: true if each kind of bracket (), [] and {} in expression are paired correctly, false otherwise.

Constraints

expression contains less than 2048 characters.

Example

Input

{([]){}()}

Output

true

Solve it

A higher resolution is required to access the IDE