human
Can you provide a Python program to print `Yes` given the following:
A bracket sequence is a string that is one of the following:

1. An empty string;
2. The concatenation of `(`, A, and `)` in this order, for some bracket sequence A ;
3. The concatenation of A and B in this order, for some non-empty bracket sequences A and B /


Given are N strings S_i. Can a bracket sequence be formed by concatenating all the N strings in some order?

Constraints

* 1 \leq N \leq 10^6
* The total length of the strings S_i is at most 10^6.
* S_i is a non-empty string consisting of `(` and `)`.

Input

Input is given from Standard Input in the following format:

N
S_1
:
S_N

Output

If a bracket sequence can be formed by concatenating all the N strings in some order, print `Yes`.
otherwise, print `No`.

Examples

Input

2
)
(()

Output

Yes

Input

2
)(
()

Output

No

Input

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

Output

Yes

Input

3
(((
)
)

Output

No
Using python can you solve the prior task?
assistant
#Here is Python program to print `Yes`.

# Hello from https://codeforces.com/gym/101341/problem/A

class BracketString:
    def __init__(self, s, i):
        self.i = i
 
        balance = 0
        minimum = 0
        for c in s:
            if c == "(":
                balance += 1
            else:
                balance -= 1
                minimum = min(minimum, balance)
 
        revBalance = 0
        revMinimum = 0
        for c in reversed(s):
            if c == ")":
                revBalance += 1
            else:
                revBalance -= 1
                revMinimum = min(revMinimum, revBalance)
 
        assert balance == -revBalance
 
        self.balance = balance
        self.minimum = minimum
        self.revMinimum = revMinimum
 
    @staticmethod
    def cmpForPositive(a, b):
        return b.minimum - a.minimum
 
    @staticmethod
    def cmpForNegative(a, b):
        return a.revMinimum - b.revMinimum
 
 
n = int(raw_input())
positive = []
negative = []
neutral = []
sumBalance = 0
for i in xrange(n):
    s = raw_input()
    bs = BracketString(s, i)
    if bs.balance > 0:
        positive.append(bs)
    elif bs.balance < 0:
        negative.append(bs)
    else:
        neutral.append(bs)
    sumBalance += bs.balance
 
if sumBalance != 0:
    print "No"
    exit()
 
positive.sort(cmp=BracketString.cmpForPositive)
negative.sort(cmp=BracketString.cmpForNegative)
 
ans = []
curBalance = 0
 
for bs in positive + neutral + negative:
    if curBalance + bs.minimum < 0:
        print "No"
        exit()
    curBalance += bs.balance
    ans.append(bs.i + 1)
 
print "Yes"