Description

Natsuzora 有一个 $n\times n$ 的 $01$ 矩阵，他想要把这个矩阵变成完全上三角矩阵。

完全上三角矩阵的定义如下：如果一个 $01$ 矩阵 $a$ 是完全上三角矩阵，那么当 $i\leq j$ 时，$a_{i,j}=1$；否则，$a_{i,j}=0$。

为了便于理解，这里给出一个 $4\times 4$ 的完全上三角矩阵的例子：

$$\begin{bmatrix} 1&1&1&1\\ 0&1&1&1\\ 0&0&1&1\\ 0&0&0&1 \end{bmatrix} $$

Natsuzora 可以对矩阵进行任意次操作，每次操作为如下两种之一：

• 选择两个数字 $i$ 和 $j$ $(1\leq i<j\leq n)$，然后交换矩阵的第 $i$ 行和第 $j$ 行；
• 选择两个数字 $i$ 和 $j$ $(1\leq i<j\leq n)$，然后交换矩阵的第 $i$ 列和第 $j$ 列。

交换矩阵的两行的意思是将矩阵每一列中位于这两行的两个元素进行交换；交换两列也是类似的。

请你告诉 Natsuzora，他是否有可能将这个矩阵变为完全上三角矩阵。

Input

第一行一个整数 $n$ $(1\leq n\leq 100)$，表示 Natsuzora 的矩阵的大小。

接下来 $n$ 行，第 $i$ 行包含一个长度为 $n$ 的字符串 $s_i$。该字符串中只包含字符 0 或 1，其中若 $a_{i,j}=1$，则 $s_{i,j}$ 为 1；若 $a_{i,j}=0$，则 $s_{i,j}$ 为 0。

Output

若该矩阵可以变为完全上三角矩阵，输出 YES；否则，输出 NO。

Samples

4
1001
1000
1011
1111

YES

Note

对于第一个样例，以下是一个合法的操作序列：

• 交换第 $1$, $4$ 行；
• 交换第 $2$, $3$ 行；
• 交换第 $3$, $4$ 行；
• 交换第 $1$, $4$ 列；
• 交换第 $1$, $3$ 列；
• 交换第 $1$, $2$ 列。

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛