You are given $n$ strings $\mathit{str}_1, \mathit{str}_2, \ldots, \mathit{str}_n$, each consisting of `(`

and `)`

. The objective is to determine whether it is possible to permute the $n$ strings so that the concatenation of the strings represents a *valid* string.

Validity of strings are defined as follows:

- The empty string is valid.
- If $A$ and $B$ are valid, then the concatenation of $A$ and $B$ is valid.
- If $A$ is valid, then the string obtained by putting $A$ in a pair of matching parentheses is valid.
- Any other string is not valid.

For example, "()()" and "(())" are valid, while "())" and "((()" are not valid.

The first line of the input contains an integer $n$ ($1 \leq n \leq 100$), representing the number of strings. Then $n$ lines follow, each of which contains $\mathit{str}_i$ ($1 \leq \lvert \mathit{str}_i \rvert \leq 100$). All characters in $\mathit{str}_i$ are `(`

or `)`

.

Output a line with "Yes" (without quotes) if you can make a valid string, or "No" otherwise.

3 ()(()(( ))()()(() )())(())

Yes

2 ))()(( ))((())(

No

Source: Japan Alumni Group Spring Contest 2014
, Japan, 2014-04-13

http://acm-icpc.aitea.net/

http://jag2014spring.contest.atcoder.jp/

http://acm-icpc.aitea.net/

http://jag2014spring.contest.atcoder.jp/