Chocolate

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid of domino pieces, decide whether a full horizontal or vertical cut can split the bar without cutting through any piece.

Level: Medium5 of 10
Topics: Implementation, Array, Matrix, Brute force
Solved: No attempts yet

Problem

Petya loves chocolate very much. Masha loves chocolate very much too. Recently Petya bought a chocolate bar and now he wants to share it with Masha. The chocolate bar is an $n \times m$ rectangle filled entirely with small chocolate pieces, each a $2 \times 1$ rectangle.

Petya splits the bar into two parts by breaking it along a line parallel to one of its sides. Neither Petya nor Masha likes broken pieces, so Petya wants to break the bar without damaging any piece.

Help Petya share the chocolate with Masha.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 20$ ; at least one of $n$ and $m$ is even). The next $n$ lines contain $m$ numbers each: the numbers of the pieces that contain the corresponding cells of the bar. The pieces are numbered from $1$ to $\frac{n \cdot m}{2}$ , and no two pieces share a number.

Output

Print <<Yes>> if Petya can break the bar without damaging any piece. Otherwise print <<No>>.

Examples2

Example 1
Input
```
2 3
1 1 2
3 3 2
```
Expected output
```
Yes
```

Example 2

Input

5 6
1 2 2 3 3 4
1 5 6 7 7 4
8 5 6 9 10 10
8 11 11 9 12 13
14 14 15 15 12 13

Expected output

No