Multiplication Table

Time limit: 0.7s Memory limit: 256MB Input: Output:

Bob has just started exploring the fascinating world of mathematics.
One day, his teacher introduced him to the multiplication table - an infinite grid where the value at row ii and column jj (for all integers i,j>0i, j > 0) is simply iji\cdot j.

Bob was fascinated and began practicing with a small section of the table.

However, while Bob was taking a break, his mischievous friend scribbled over Bob's worksheet, replacing some of the numbers with either incorrect values or question marks (?).
Formally, he is left with a table of NN rows and MM columns, where each cell contains either:

  • A positive integer, or
  • A question mark (?) indicating an unknown or erased value.

Now Bob isn't sure if what he has is still a valid piece of the multiplication table. Can you help Bob figure it out?

Your task is to determine whether it's possible to replace the question marks with positive integers such that the entire table corresponds to a valid subrectangle
of the infinite multiplication table.
You do not need to find the missing numbers - just decide whether such a valid completion exists.

Input data

The first line contains the integers NN, MM, representing the number of rows and columns in Bob's table.

This is followed by NN lines, where line ii (i=0,1,,N1i = 0, 1, \ldots, N - 1) represents row ii of Bob's table (Pi,0,Pi,1,,Pi,M1P_{i,0}, P_{i,1}, \ldots, P_{i,M-1}),
consisting of question marks and integers.

Output data

  • Print YES if the table can be a part of the multiplication table after filling in the question marks.
  • Print NO if it is impossible.

Constraints and clarifications

  • 1NM10000001 \le N\cdot M \le 1\,000\,000.
  • Pi,j=P_{i,j}= ? or 1Pi,j10121 \le P_{i,j} \le 10^{12} for each i=0N1i=0\ldots N-1, j=0M1j=0\ldots M-1.
# Score Restrictions
0 0 Examples
1 12 N,M10N,M \le 10, 1Pi,j10 0001 \le P_{i,j} \le 10 \ 000, and the table contains no ?
2 11 N,M100N,M \le 100, Pi,j=P_{i,j}= ? or 1Pi,j10 0001 \le P_{i,j} \le 10 \ 000.
3 26 N,M102N,M \le 10^2, Pi,j=P_{i,j}= ? or 1Pi,j1081 \le P_{i,j} \le 10^8.
4 51 No additional limitations.

Example 1

stdin

2 4
6 ? ? ?
? ? ? 18

stdout

YES

Explanation

In the first sample case the answer is YES.
Please note that this does not mean, that we can identify the part of the multiplication table. Here we have two possibilities.

Example 2

stdin

2 2
? ?
? 3

stdout

NO

Explanation

In the second sample case either the first row or the first column is outside the multiplication table, as the number 33
only appears in the first row or the first column of the infinite grid.

Example 3

stdin

2 1
999997000002
999998000001

stdout

YES

Log in or sign up to be able to send submissions!