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.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Obj> listA = new ArrayList<>();
    ArrayList<Obj> listB = new ArrayList<>();
    for(int i = 0; i < n; i++){
      String s = sc.next();
      int left = 0;
      int right = 0;
      for(int j = 0; j < s.length(); j++){
        if(s.charAt(j) == '('){
          left++;
        } else if(s.charAt(j) == ')'){
          if(left > 0){
            left--;
          } else {
            right++;
          }
        }
      }
      Obj obj = new Obj(left,right);
      if(obj.left > obj.right){
        listA.add(obj);
      } else {
        listB.add(obj);
      }
    }
    if(solve(listA, listB)){
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }
  static boolean solve(ArrayList<Obj> listA, ArrayList<Obj> listB){
    listA.sort((o1, o2) -> o1.right - o2.right);
    listB.sort((o1, o2) -> o2.left - o1.left);
    int temp = 0;
    for(Obj a : listA){
      temp -= a.right;
      if(temp < 0) return false;
      temp += a.left;
    }
    for(Obj a : listB){
      temp -= a.right;
      if(temp < 0) return false;
      temp += a.left;
    }
    if(temp != 0) return false;
    return true;
  }

  static class Obj {
    int left;
    int right;
    public Obj(int left, int right){
      this.left = left;
      this.right = right;
    }
  }
}