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;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<ll, ll>P;

int main(){
  ll N;
  cin>>N;
  vector<P>Sup;
  vector<P>Sdown;
  rep(i,N){
  	string s;
  	cin>>s;
    ll total=0,mini=0;
    rep(j,s.size()){
      if(s[j]=='('){total++;}
      else{total--;}
      mini=min(mini,total);
    }
    if(total>=0){Sup.push_back(P(mini,total));}
    else{Sdown.push_back(P(mini-total,-total));}
  }
  sort(Sup.begin(),Sup.end());
  reverse(Sup.begin(),Sup.end());
  
  sort(Sdown.begin(),Sdown.end());
  reverse(Sdown.begin(),Sdown.end());
  
  int flag=0;
  ll sum1=0;
  ll sum2=0;
  rep(i,Sup.size()){
  	if(Sup[i].first<0&&sum1+Sup[i].first<0){flag=1;}
  	else{sum1+=Sup[i].second;}
    if(sum1<0){flag=1;}
  }
  rep(i,Sdown.size()){
  	if(Sdown[i].first<0&&sum2+Sdown[i].first<0){flag=1;}
  	else{sum2+=Sdown[i].second;}
    if(sum2<0){flag=1;}
  }
  if(sum1!=sum2){flag=1;}
  if(flag==1){cout<<"No";}
  if(flag==0){cout<<"Yes";}
}
