You have a grid of N rows and M columns. Each cell in this grid contains an integer. The cell at row x and column y is denoted by (x, y), and initially contains value Gx,y.
In one move you can:
Select a cell A. Let the coordinates of A be (i, j).
Select a cell B. Let the coordinates of B be (x, y).
It must be that abs(i - x) = 1 and j = y, or abs(j - y) = 1 and i = x.
Select any integer X. X can be positive, negative, or even zero.
Add X to cell A, and add X to cell B.
Note that in a move, you must perform all those steps in order.
Output Yes if it is possible to perform any number of operations (possibly zero), such that every cell has value C afterward, or No if it is not possible.
Input Format
The first line of input contains three space-separated integers, N, M and C. N is the number of rows, M is the number of columns, C is the target value of every cell in the grid after all operations.
The following N lines of input each contain M space-separated integers. The j-th integer on the i-th such line contains Gi, j, which is the value of the cell (i, j) in the input grid.
Output Format
Output Yes if it is possible to use the operation described above any number of times (possibly even zero times), in order to convert the grid such that every cell of the grid ends up containing C. If it is not possible, output No.
In all test data, it is guaranteed that:
1 ≤ N, M ≤ 1000
-109 ≤ C ≤ 109
-109 ≤ Gi,j ≤ 109 for all 1 ≤ i ≤ N and 1 ≤ j ≤ M.
Subtasks
Subtask 1 (16 points): N = 1 and M = 2
Subtask 2 (22 points): N = 1
Subtask 3 (18 points): N·M ≤ 1000
Subtask 4 (21 points): C = 0
Subtask 5 (23 points): No additional constraints.
Approach and code please help me