시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
0.3 초 256 MB 1 1 (100%) 1
문제
Peter는 등차수열에 대한 수업을 듣고 과제로 종이 한 장을 받았는데, 종이에는 숫자가 들어있는 $R \times C$ 크기의 격자가 적혀있었다. 그중 일부의 칸들은 비어있었다. 이때 비어있는 칸들에 숫자를 채워서 등차사각형을 만드는 것이 Peter의 과제이다. 등차사각형에서는 각 행과 열의 숫자들이 그들이 적혀있는 순서대로 등차수열을 이루어야 한다. 예를 들면, 이것은 $3 \times 5$ 크기의 등차사각형이다. ``` 1 3 5 7 9 2 2 2 2 2 3 1 -1 -3 -5 ``` Peter는 직접 과제를 하기 귀찮아하고 당신이 이 과제를 풀어줄 프로그램을 만들어주길 원한다. 정수와 점들이 들어있는 격자를 받았을 때 점이 들어있는 위치에 유리수를 넣어서 등차사각형을 만드는 것이 가능한지 확인하는 프로그램을 작성하라. 그리고 가능한 해가 있다면 그중 하나를 찾아라. 참고: 등차수열은 연속하는 두 항의 차이가 모두 일정한 수열이다.
입력
첫째 줄에 격자의 행과 열의 수 $R, C$가 주어진다. 다음 $R$개 줄에는 띄어쓰기로 구분된 $C$개의 정수 혹은 점(.)이 들어온다.
출력
해가 존재하지 않는다면 문자열 "No Solution."(따옴표는 출력하지 않는다) 한 줄을 출력한다. 여러 개의 해가 존재할 경우 임의로 하나만 고르면 된다. $R$개의 행을 출력해야 하며 각 행은 띄어쓰기로 구분된 $C$개의 유리수로 이루어져 있어야 한다. 각 유리수들은 "$N/D$"(분자/분모, 역자주)꼴로 출력되어야 한다. $N$과 $D$는 서로소이며 D는 양수여야 하고 만약 $D$가 $1$이라면 "$/D$" 부분을 생략해라. 출력의 숫자들은 $20$자리를 넘어서는 안 된다. (이 제한을 지키는 데는 문제가 없을 것이며 채점의 용이성을 위한 조건이다.)
힌트
#### 제약조건 격자안의 숫자는 $-150$이상 $150$이하이다. 테스트 케이스는 각각 $10$점씩 $10$개의 부분문제로 나눠지고 $1$ ~ $9$번 부분문제에서는 $1 \le R, C \le 6$ 이다. 각 부분문제에 대한 설명은 아래와 같다. ``` 부분문제 1. 모든 숫자가 채워진 상태. 부분문제 2. R = 1 이거나 C = 1. 부분문제 3. R = C = 2. 부분문제 4. 유일한 해가 존재하며 첫 번째 예시에서 제시하는 방법대로 찾을 수 있음. 부분문제 5. 정수만으로 이루어진 유일한 해 존재. 부분문제 6. 유일한 해 존재. 부분문제 7. 정수만으로 이루어진 유일한 해를 가지거나 해가 존재하지 않는다. 부분문제 8. 유일한 해를 가지거나 해가 존재하지 않는다. 부분문제 9. 임의의 테스트 케이스 부분문제 10. 1 ≤ R, C ≤ 50 인 임의의 테스트 케이스. ``` 시간 제한은 $0.3$초, 메모리 제한은 $256MB$이다. #### 예제 입력 1 ``` 3 5 . . 3 . 5 . . . 5 . . . . . 7 ``` #### 예제 출력 1 ``` 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 ``` 위 예시는 다음과 같이 풀 수 있다. 우선 두 번째 행의 마지막 열은 6이 들어가야 함을 알 수 있다. 그 후 첫 번째, 두 번째 행은 자명하게 채울 수 있고 그를 통해 세 번째 행을 완성하면 된다. #### 예제 입력 2 ``` 1 6 4 . . 0 . . ``` #### 예제 출력 2 ``` 4 8/3 4/3 0 -4/3 -8/3 ``` #### 예제 입력 3 ``` 1 4 1 2 . 2 ``` #### 예제 출력 3 ``` No solution. ``` #### 예제 입력 4 ``` 3 3 1 . . . 2 . . . 3 ``` #### 예제 출력 4 ``` 1 2 3 1 2 3 1 2 3 ``` 이것은 가능한 여러 개의 해 중 하나이다.