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
#include <bits/stdc++.h>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<int> sum(N,0),Min(N,0);
    int Sum=0;
    for (int i=0;i<N;++i){
        string S; cin >> S;
        for (int j=0;j<S.size();++j){
            sum[i]+=(S[j]=='('?1:-1);
            Min[i]=min(Min[i],sum[i]);
        }
        Sum+=sum[i];
    }
    int ans=1;
    if (Sum!=0) ans=0;
    vector<pair<int,int>> v1,v2;
    Sum=0;
    for (int i=0;i<N;++i){
        if (Min[i]>=0) Sum+=sum[i];
        else if (sum[i]>=0) v1.emplace_back(-Min[i],sum[i]);
        else v2.emplace_back(Min[i]-sum[i],Min[i]);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    for (auto p:v1){
        if (Sum-p.first<0) ans=0;
        Sum+=p.second;
    }
    for (auto p:v2){
        int M=p.second,s=M-p.first;
        if (Sum+p.second<0) ans=0;
        Sum+=p.second-p.first;
    }
    cout << (ans?"Yes":"No") << '\n';
}