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
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説通りに実装したソースコード
 * 
 * https://atcoder.jp/contests/abc167/submissions/13128568 にも参照
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			List<Data> ls = new ArrayList<>(), rs = new ArrayList<>();
			long sum = IntStream.range(0, n).mapToLong(i -> {
				char[] s = scanner.next().toCharArray();
				int total = 0, min = 0;
				for (char c : s) {
					total += ('(' == c) ? 1 : -1;
					min = Math.min(total, min);
				}
				if (total >= 0) {
					ls.add(new Data(total, min));
				} else {
					rs.add(new Data(-total, min - total));
				}
				return total;
			}).sum();
			Collections.sort(ls);
			Collections.sort(rs);
			System.out.println((check(ls) && check(rs) && (sum == 0L)) ? "Yes" : "No");
		}
	}

	/**
	 * リストの実現可能性をチェックする
	 * 
	 * @param list データのリスト
	 * @return リストが実現可能かどうか
	 */
	private static boolean check(List<Data> list) {
		long total = 0L;
		for (Data data : list) {
			if (total + data.min < 0) {
				return false;
			}
			total += data.total;
		}
		return true;
	}

	/**
	 * 個々のsを表す用クラス
	 */
	private static class Data implements Comparable<Data> {
		int total;
		int min;

		public Data(int total, int min) {
			super();
			this.total = total;
			this.min = min;
		}

		@Override
		public int compareTo(Data o) {
			return Integer.compare(o.min, this.min);
		}
	}
}
