마법 직사각형

시간 제한1초메모리 제한1024 MB

요약

주어진 격자의 지워진 수를 유리수로 채워 모든 행과 열이 등차수열인 마법 직사각형을 만들 수 있으면 출력하고, 아니면 ej magisk를 출력합니다.

난이도: 보통10점 중 7점
유형: 수학, 구현, 행렬
정답자: 아직 제출이 없습니다

문제

길이 $n+1$ 인 마법 수열은 $a, a+d, a+2d, \ldots, a+nd$ 꼴로 나타나는 수열이다. 여기서 $a$ 와 $d$ 는 유리수이다. 예를 들어 $2, 5.5, 9, 12.5$ , $5, 5, 5$ , $2, 1, 0, -1, -2$ 는 모두 마법 수열이다.

크기가 $R \times C$ 인 마법 직사각형은 모든 행과 모든 열이 마법 수열인 직사각형이다.

일부 수가 지워진 정수 직사각형이 주어질 때, 지워진 수를 채워 넣어 직사각형을 마법 직사각형으로 만들 수 있는지 판정한다.

입력

입력의 첫째 줄에는 주어진 직사각형의 행 수와 열 수인 $R$ 과 $C$ 가 주어진다. 이어서 $R$ 개의 줄에 각각 $C$ 개의 정수가 주어진다.

지워진 수는 마침표(.)로 나타낸다.

출력

해가 없으면 ej magisk를 출력한다.

그렇지 않으면 $R$ 개의 줄에 $C$ 개의 수를 출력한다. 이는 입력 직사각형에서 지워진 수를 바꿔 넣은 마법 직사각형이다.

유리수는 N/D 형식으로 출력하며, $N$ 과 $D$ 는 각각 100자리 이하이다. 수와 나눗셈 기호 사이에는 공백을 넣지 않는다. $D=1$ 이면 N으로 쓸 수 있다.

제한

처음 9개 테스트 케이스에서는 $1 \le R, C \le 6$ 이다.

예제4

예제 1

입력

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

예상 출력

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

예제 2
입력
```
1 6
4 . . 0 . .
```
예상 출력
```
4 8/3 4/3 0 -4/3 -8/3
```
예제 3
입력
```
1 4
1 2 . 2
```
예상 출력
```
ej magisk
```

예제 4

입력

3 3
1 . .
. 2 .
. . 3

예상 출력

1 0 -1
3 2 1
5 4 3