括号序列排列

题目描述

将满足以下任一条件的字符串定义为括号序列:

• 空字符串
• 存在某个括号序列 $A$,将 (, $A$, ) 按此顺序连接得到的字符串
• 存在非空括号序列 $A$, $B$,将 $A$, $B$ 按此顺序连接得到的字符串

给出 $N$ 个字符串 $S_i$。将全部 $S_i$ 按任意顺序连接时,能否构成一个括号序列?

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$
$:$
$S_N$

输出格式

如果按任意顺序连接 $S_i$ 能构成括号序列,输出 Yes;否则输出 No。

样例

2
)
(()

Yes

按 ((), ) 的顺序连接就构成了括号序列。

2
)(
()

No

4
((()))
((((((
))))))
()()()

Yes

3
(((
)
)

No

数据范围

• $1 \leq N \leq 10^6$
• $S_i$ 的字符串长度总和不超过 $10^6$
• $S_i$ 是仅由 (, ) 组成的非空字符串