There is a rectangular grid of _n_ rows of _m_ initially-white cells each.
Arkady performed a certain number (possibly zero) of operations on it. In the _i_\-th operation, a non-empty subset of rows _R__i_ and a non-empty subset of columns _C__i_ are chosen. For each row _r_ in _R__i_ and each column _c_ in _C__i_, the intersection of row _r_ and column _c_ is coloured black.
There's another constraint: a row or a column can only be chosen at most once among all operations. In other words, it means that no pair of (_i_, _j_) (_i_ < _j_) exists such that or , where denotes intersection of sets, and denotes the empty set.
You are to determine whether a valid sequence of operations exists that produces a given final grid.
## Input
The first line contains two space-separated integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 50) — the number of rows and columns of the grid, respectively.
Each of the following _n_ lines contains a string of _m_ characters, each being either '_._' (denoting a white cell) or '_#_' (denoting a black cell), representing the desired setup.
## Output
If the given grid can be achieved by any valid sequence of operations, output "_Yes_"; otherwise output "_No_" (both without quotes).
You can print each character in any case (upper or lower).
[samples]
## Note
For the first example, the desired setup can be produced by 3 operations, as is shown below.
<center></center>For the second example, the desired setup cannot be produced, since in order to colour the center row, the third row and all columns must be selected in one operation, but after that no column can be selected again, hence it won't be possible to colour the other cells in the center column.
Let $ G \in \{0,1\}^{n \times m} $ be the given grid, where $ G_{r,c} = 1 $ if cell $ (r,c) $ is black, and $ 0 $ if white.
Let $ \mathcal{R} \subseteq 2^{[n]} $ and $ \mathcal{C} \subseteq 2^{[m]} $ be collections of non-empty row and column subsets, respectively, such that:
- Each row index appears in at most one set in $ \mathcal{R} $,
- Each column index appears in at most one set in $ \mathcal{C} $,
- For every operation $ i $, there exists $ R_i \in \mathcal{R} $, $ C_i \in \mathcal{C} $, and the black cells are exactly $ \bigcup_{i} (R_i \times C_i) $.
Then, the grid $ G $ is achievable if and only if there exist such $ \mathcal{R} $ and $ \mathcal{C} $ satisfying:
$$
G_{r,c} = 1 \iff \exists\, R \in \mathcal{R},\, C \in \mathcal{C} \text{ such that } r \in R \text{ and } c \in C.
$$
Equivalently, define:
- $ \mathcal{R}^* = \{ R \subseteq [n] \mid \exists\, c \in [m] \text{ s.t. } \forall r \in R,\, G_{r,c} = 1 \text{ and } \forall r \notin R,\, G_{r,c} = 0 \} $ — the set of all row patterns corresponding to some column $ c $,
- $ \mathcal{C}^* = \{ C \subseteq [m] \mid \exists\, r \in [n] \text{ s.t. } \forall c \in C,\, G_{r,c} = 1 \text{ and } \forall c \notin C,\, G_{r,c} = 0 \} $ — the set of all column patterns corresponding to some row $ r $.
Then $ G $ is achievable if and only if:
$$
\forall r \in [n],\, \forall c \in [m]:\quad G_{r,c} = 1 \iff \exists\, R \in \mathcal{R}^*,\, C \in \mathcal{C}^* \text{ s.t. } r \in R \text{ and } c \in C.
$$
Moreover, the sets in $ \mathcal{R}^* $ must be pairwise disjoint, and the sets in $ \mathcal{C}^* $ must be pairwise disjoint.
Thus, the necessary and sufficient condition is:
> The row patterns (i.e., the distinct row vectors of $ G $) must be pairwise disjoint in support, and the column patterns (i.e., the distinct column vectors of $ G $) must be pairwise disjoint in support, and the grid must be the Cartesian product of its row pattern sets and column pattern sets.
**Formal Criterion:**
Let $ \mathcal{R}_{\text{patterns}} = \{ \text{row}_r \mid r \in [n] \} \subseteq \{0,1\}^m $, the set of distinct row vectors.
Let $ \mathcal{C}_{\text{patterns}} = \{ \text{col}_c \mid c \in [m] \} \subseteq \{0,1\}^n $, the set of distinct column vectors.
Define:
- $ R_p = \{ r \in [n] \mid \text{row}_r = p \} $ for each $ p \in \mathcal{R}_{\text{patterns}} $,
- $ C_q = \{ c \in [m] \mid \text{col}_c = q \} $ for each $ q \in \mathcal{C}_{\text{patterns}} $.
Then $ G $ is achievable if and only if:
1. The sets $ \{ R_p \mid p \in \mathcal{R}_{\text{patterns}} \} $ form a partition of $ [n] $ (i.e., are pairwise disjoint and cover all rows),
2. The sets $ \{ C_q \mid q \in \mathcal{C}_{\text{patterns}} \} $ form a partition of $ [m] $ (i.e., are pairwise disjoint and cover all columns),
3. For all $ r \in [n] $, $ c \in [m] $:
$$
G_{r,c} = 1 \iff \text{row}_r \text{ has a } 1 \text{ in column } c.
$$
But since row patterns are fixed, this reduces to:
$$
G_{r,c} = 1 \iff \text{the pattern of row } r \text{ has a } 1 \text{ at position } c.
$$
Which is always true by definition.
The **key constraint** is that the row patterns must be such that if two rows have the same pattern, they are assigned to the same $ R_i $, and similarly for columns. But the **real constraint** is: **if two rows have different patterns, then their 1-positions must not overlap in a way that forces a column to be used in multiple operations.**
Actually, the correct necessary and sufficient condition is:
> The grid $ G $ can be expressed as the union of axis-aligned rectangles (i.e., Cartesian products $ R_i \times C_i $) where the $ R_i $ are pairwise disjoint row subsets and the $ C_i $ are pairwise disjoint column subsets.
This is equivalent to:
> For any two black cells $ (r_1, c_1) $ and $ (r_2, c_2) $, if $ G_{r_1, c_2} = 0 $ or $ G_{r_2, c_1} = 0 $, then $ r_1 $ and $ r_2 $ cannot be in the same row group, and $ c_1 $ and $ c_2 $ cannot be in the same column group.
But a simpler characterization:
**Theorem:** A grid $ G $ is representable as a disjoint union of rectangles $ R_i \times C_i $ with disjoint row and column sets if and only if:
> For any two rows $ r_1, r_2 $, either $ \text{row}_{r_1} \subseteq \text{row}_{r_2} $, or $ \text{row}_{r_2} \subseteq \text{row}_{r_1} $, or $ \text{row}_{r_1} \cap \text{row}_{r_2} = \emptyset $.
Similarly for columns.
Actually, even simpler:
> The grid must be **rectangle-constructible with disjoint row/column sets** if and only if **every connected component of black cells forms a rectangle**, and **no two rectangles share a row or a column**.
But the cleanest formal condition:
Let $ \mathcal{R}_{\text{max}} = \{ R \subseteq [n] \mid \exists C \subseteq [m],\, R \times C \subseteq G \text{ and } R \text{ is maximal} \} $, and similarly for columns.
But the known solution in competitive programming is:
> A grid is achievable if and only if for every pair of rows $ i, j $, the set of columns where row $ i $ is black is either a subset of, or disjoint from, the set of columns where row $ j $ is black.
**Formal Statement:**
Let $ S_r = \{ c \in [m] \mid G_{r,c} = 1 \} $ be the set of black columns in row $ r $.
Then, the grid is achievable if and only if:
$$
\forall r_1, r_2 \in [n]: \quad S_{r_1} \subseteq S_{r_2} \quad \text{or} \quad S_{r_2} \subseteq S_{r_1} \quad \text{or} \quad S_{r_1} \cap S_{r_2} = \emptyset.
$$
This condition is necessary and sufficient.
**Proof sketch:**
- If two rows have overlapping but neither contains the other, then their intersection forces a column to be used in two different operations (once with each row group), violating the "each column used at most once" constraint.
- The condition ensures that the row sets can be partitioned into a chain of inclusions or disjoint sets, and each maximal antichain (in the inclusion order) can be assigned a unique column set.
Thus, the final formal condition is:
$$
\boxed{
\forall r_1, r_2 \in [n]:\quad S_{r_1} \subseteq S_{r_2} \quad \lor \quad S_{r_2} \subseteq S_{r_1} \quad \lor \quad S_{r_1} \cap S_{r_2} = \emptyset
}
$$
where $ S_r = \{ c \in [m] \mid G_{r,c} = 1 \} $.