Magic Rectangle

Time limit1sMemory limit1024 MB

Summary

Fill the erased entries of the given integer grid, using rational values, so every row and column is an arithmetic sequence, or print ej magisk if impossible.

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

Problem

A magic sequence of length $n+1$ is a sequence of the form $a, a+d, a+2d, \ldots, a+nd$ , where $a$ and $d$ are rational numbers. For example, $2, 5.5, 9, 12.5$ , $5, 5, 5$ , and $2, 1, 0, -1, -2$ are magic sequences.

A magic rectangle of size $R \times C$ is a rectangle in which every row and every column is a magic sequence.

Given a rectangle of integers with some numbers erased, determine whether the erased numbers can be filled in so that the rectangle is a magic rectangle.

Input

The first line of the input contains $R$ and $C$ , the number of rows and columns in the given rectangle. The next $R$ lines each contain $C$ integers.

An erased number is represented by a period (.).

Output

If no solution exists, print ej magisk.

Otherwise, print $R$ lines, each containing $C$ numbers: a magic rectangle obtained by replacing the erased numbers in the input rectangle.

Rational numbers must be written in the form N/D, where $N$ and $D$ are each at most 100 digits long. There must be no spaces between the numbers and the division sign. If $D=1$ , you may write N.

Constraints

In the first 9 test cases, $1 \le R, C \le 6$ .

Examples4

Example 1

Input

3 5
. . 3 . 5
. . . 5 .
. . . . 7

Expected output

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

Example 2
Input
```
1 6
4 . . 0 . .
```
Expected output
```
4 8/3 4/3 0 -4/3 -8/3
```
Example 3
Input
```
1 4
1 2 . 2
```
Expected output
```
ej magisk
```

Example 4

Input

3 3
1 . .
. 2 .
. . 3

Expected output

1 0 -1
3 2 1
5 4 3