Arithmetic Sequences in Matrix

Given an R × C matrix, some cells already contain an integer while some cells are empty (denoted by a dot '.'). Your task is to fill the empty cells with integers such that the numbers in every row (read from left to right) and every column (read from top to bottom) form an arithmetic sequence. That is, for every row i and every column j, if we denote the filled number at cell (i, j) by \(a_{i,j}\), then for each row there exist integers \(A_i\) and \(d_i\) satisfying

[ a_{i,j} = A_i + (j-1)d_i, \quad 1 \le j \le C, ]

and for each column there exist integers \(B_j\) and \(e_j\) satisfying

[ a_{i,j} = B_j + (i-1)e_j, \quad 1 \le i \le R. ]

A careful analysis shows that a valid filling exists if and only if there exist four integers \(A, B, C, D\) such that for every cell (i, j) (with indices starting from 1) the following holds:

[ a_{i,j} = A + (i-1)C + (j-1)\Bigl(B + (i-1)D\Bigr). ]

You are given some cells with fixed values. Use these equations to deduce (or arbitrarily choose if free) the parameters and then fill the remaining cells accordingly so that every row and column forms an arithmetic progression.

inputFormat

The first line of input contains two integers R and C (the number of rows and columns). Each of the next R lines contains C tokens separated by spaces. A token is either a number (which may be negative) or a dot '.' indicating an empty cell.

outputFormat

Output the completed matrix in R lines. Each line should contain C integers separated by a single space. The filled matrix must guarantee that each row and column forms an arithmetic progression.

sample

3 3
1 . 5
. . .
9 . 13

1 3 5
5 7 9
9 11 13