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>
#define pb emplace_back
using namespace std;
using ll = long long;
#define FI(i) (puts((i) ? "Yes" : "No"), exit(0))
const int maxn = 1e6+2;
int n;
pair<int,int> a[maxn];
bool solve(vector<pair<int,int>> &v) {
	int now = 0;
	reverse(v.begin(), v.end());
	for (auto [low, c] : v) {
		if (now + low < 0) return false;
		now += c;
	}
	return true;
}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	int sum = 0;
	vector<pair<int,int>> pos, neg;
	for (int i = 0;i < n;++i) {
		string w;
		cin >> w;
		int c = 0, low = 0;
		for (char j : w) {
			c += (j == '(' ? 1 : -1);
			low = min(low, c);
		}
		sum += c;
		if (c >= 0) pos.pb(low, c);
		else {
			c = 0, low = 0;
			while (w.size()) {
				c += (w.back() == ')' ? 1 : -1);
				low = min(low, c);
				w.pop_back();
			}
			neg.pb(low, c);
		}
	}
	if (sum != 0) 
		FI(0);
	sort(pos.begin(), pos.end());
	sort(neg.begin(), neg.end());
	FI(solve(pos) && solve(neg));
}

