题目内容

地下管廊巡检员沿着一条管段记录封口卡。记录写成字符串 $t$，其中只会出现三种封口：圆口 ( 与 )、方口 [ 与 ]、抱箍 { 与 }（也可能一种都不出现）。一份记录视为合格，当且仅当它是有效的封口序列。

有效封口序列的定义：

• 封口必须成对扣上（如 ()、[]、{} 合法）；
• 允许嵌套（如 ([])、{{[]}} 合法）；
• 不允许交叉（如 ([)] 非法）；
• 空记录（长度为 0）视为合法。

请判断给定记录是否合格。

约束：

• 0 $\le$ $|t|$ $\le$ 100000
• $t$ 仅由 (、)、[、]、{、} 组成

输入描述

一行字符串 $t$，表示沿管段写下的封口记录，可以为空。

输出描述

如果记录合格，输出 true；否则输出 false。

样例1

输入

[()]{}

输出

true

说明

方口包住圆口，再并列一副抱箍，全部成对且不交叉。

样例2

输入

([)]

输出

false

说明

圆口与方口交叉，不能扣上。

样例3

输入

输出

true

说明

输入是空串，按定义视为合法。