Aerophotography data provide a bitmap picture of a hard-to-reach region. According to the suggestions of scientists, this region is a cemetery of an extinct civilization. Indeed, the picture, having been converted to a binary form, shows distinctly visible areas, dark (marked with symbols 1) and light (marked with 0). It seems that the dark areas are tombstones. It's easy to either confirm or reject the hypothesis since the race that lived in the region knew astronomy, so tombstones were always oriented along the Earth's parallels and meridians. That is why the dark areas in the picture should have the form of rectangles with the sides parallel to the axes. If it is so, then we indeed have a picture of a cemetery of an extinct race. Otherwise, new hypotheses should be suggested.
Input
The first input line contains two integers N and M, which are the dimensions of the picture provided by the aerophotography. Each of the next N lines contains M zeros or ones separated with a space. The numbers N and М do not exceed 3000.
Output
Output "Yes" if all connected dark areas in the picture are rectangles and "No" otherwise.
Samples
input | output |
---|
2 2
0 1
1 1
| No
|
3 3
0 0 1
1 1 0
1 1 0
| Yes
|
Problem Author: Nikita Shamgunov and Leonid Volkov
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003