Problem B
Bracket Matrix

Image by GamerDruid

A bracket sequence consisting of ‘(’ and ‘)’ is defined to be valid as follows:

1. An empty sequence is valid.

2. If $x$ is a valid bracket sequence, then $(x)$ is a valid bracket sequence.

3. If $x$ and $y$ are valid bracket sequences, then the concatenation of $x$ and $y$, $z=xy$, is a valid bracket sequence.

You are given a bracket matrix of size $n \times n$, in which each cell has a single bracket. Each row of the matrix, read from left to right, presents a bracket sequence. You may modify the matrix by choosing two brackets in a same column and swapping their positions. You may make any number of swaps (possibly zero). Can you make every row of the matrix present a valid bracket sequence?

Input

The first line has an even integer $n$ ($2 \leq n \leq 2\, 000$). Each of the next $n$ lines has $n$ brackets giving one row of the bracket matrix.

Output

If you can obtain a valid bracket sequence on every row of the matrix, output “Yes”. Otherwise, output “No”.

4
((()
()))
()))
((()

Yes

2
()
)(

No