Lexicographically Smallest Tiling Verification

You are given a room floor divided into an n × m grid. Each cell of the grid is tiled with a square tile of a certain color, represented by a lowercase letter. A tiling is considered valid if no two adjacent tiles (sharing an edge) have the same color.

Among all valid tilings, the lexicographically smallest tiling is defined as the one produced by filling the grid cell by cell from top‐to‐bottom and left‐to‐right, and for each cell choosing the smallest (i.e. earliest in alphabetical order) color that does not match the already assigned tile above (if any) or to the left (if any). This greedy choice guarantees that the overall concatenation of the rows (from top to bottom) is lexicographically the smallest possible.

Your task is to verify a candidate tiling. Given the grid dimensions and a candidate tiling (provided as n lines of m characters), determine whether the candidate exactly matches the lexicographically smallest valid tiling described above.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the dimensions of the grid.

The next n lines each contain a string of length m, consisting of lowercase letters, representing the candidate tiling.

outputFormat

Output a single line containing Yes if the candidate tiling is exactly the lexicographically smallest valid tiling; otherwise, output No.

sample

2 2
ab
ba

Yes