An Arithmetic Rectangle

Interview

Time limit1sMemory limit128 MB

Summary

Determine whether missing cells in a grid can be filled with rationals so every row and column becomes an arithmetic progression.

Level: Medium6 of 10
Topics: Math, Matrix, Implementation
Solved: No attempts yet

Problem

After a lesson on arithmetic progressions, the teacher gave Peter some homework: a sheet of paper with integers written in some cells of an R × C grid, while the remaining cells were left empty. Peter's task is to fill in the empty cells so that the grid becomes an arithmetic rectangle. In an arithmetic rectangle, the numbers in every row and in every column form an arithmetic progression in the order in which they appear.

For example, this is a 3 × 5 arithmetic rectangle:

 1 3 5 7 9
 2 2 2 2 2
 3 1 -1 -3 -5

You are given a grid of integers in which some cells have been replaced by dots (.). Decide whether the dots can be replaced by rational numbers so that the whole grid becomes an arithmetic rectangle.

Note: an arithmetic progression is a sequence in which the difference between any two consecutive terms is constant.

Input

The first line contains two positive integers R and C, the dimensions of the grid. Each of the next R lines contains C tokens separated by single spaces. Each token is either a dot (.) or an integer.

Output

Print Yes if every dot can be replaced by a rational number so that the whole grid becomes an arithmetic rectangle, and No otherwise.

Constraints

1 ≤ R, C ≤ 50
Every integer given in the grid is between -100 and 100, inclusive.

Examples4

Example 1
Input
```
3 5
. . 3 . 5
. . . 5 .
. . . . 7
```
Expected output
```
Yes
```
Example 2
Input
```
1 6
4 . . 0 . .
```
Expected output
```
Yes
```
Example 3
Input
```
1 4
1 2 . 2
```
Expected output
```
No
```
Example 4
Input
```
3 3
1 . .
. 2 .
. . 3
```
Expected output
```
Yes
```