시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 311 88 72 31.169%

문제

서울 Y모 대학에서 끊임없이 소음과 분진을 발생시키며 공사를 진행하던 중, 고대 유물로 추정되는 석판 하나가 발굴되었다. 이 석판은 N개의 행과 M개의 열로 나누어진 격자 형태로, 각 칸은 텅 빈 칸이거나 사람 한 명이 그려진 칸이었다. 석판은 아쉽게도 온전한 형태로 발굴되지는 않았으며, 칸들 중에는 일부가 부서져 있어 내용을 식별할 수 없는 칸도 있었다.

그 후 얼마 지나지 않아, 관련 자료를 통해 이 석판의 규칙을 알 수 있게 되었다. 이 석판에서 가능한 모든 부분 직사각형에 대해 내부의 사람 수를 구하고, 그 수들을 모두 더해서 얻는 값이 K의 배수여야 한다는 것이다. 0은 모든 수의 배수가 될 수 있다.

예를 들어, 2 × 2 크기의 아래 석판을 보자.

위 석판에는 아래와 같이 9개의 부분 직사각형이 있다.

각 부분 직사각형 내부의 합은 1, 0, 0, 1, 1, 1, 1, 1, 2가 되고, 이들의 총합은 8이 된다.

학교 측은 얻은 정보를 토대로 석판을 가능한 형태 중 하나로 복원하기 위해 연세대학교 컴퓨터과학과에 복원작업을 의뢰하었고, 자연스럽게 이 과제는 2019 교내 대회의 문제로 출제되게 되었다. 당신은 석판의 형태와 K를 입력으로 받아 석판의 복원이 가능한지 알아보고, 가능할 경우 조건을 만족하는 석판 하나를 복원해야 한다.

입력

첫째 줄에 석판의 행의 수 N과 열의 수 M, 문제에 제시된 K가 주어진다. (1 ≤ N, M ≤ 50, 2 ≤ K ≤ 2500)

둘째 줄부터 N+1번째 줄까지, 각 줄에 M개의 정수 ai,j가 공백으로 구분되어 주어진다. (ai,j ∈ { -1, 0, 1})

ai,j  = -1일 경우 석판의 i번째 행 j번째 열이 부서져 있음을, ai,j  = 0 일 경우 해당 칸이 비어 있음을, ai,j  = 1일 경우 해당 칸에 사람 한 명이 그려져 있음을 의미한다.

출력

복원이 가능할 경우 첫 줄에 1을, 불가능할 경우 -1을 출력한다.

만약 첫 줄에 1을 출력했다면, 이어 N개의 줄에 M개의 정수로 행렬에 존재하는 모든 -1을 0 또는 1로 대체하여 문제의 조건에 맞게 복원한 석판 하나를 출력한다. 입력에서 -1이 아니었던 모든 칸은 입력과 동일해야 하며, -1인 모든 칸은 0 또는 1 중 하나로 복원되어야 한다.

조건을 만족하는 석판이 여러 가지라면 아무 것이나 하나만 출력한다.

예제 입력 1

2 2 8
1 0
0 -1

예제 출력 1

1
1 0
0 1

예제 입력 2

2 2 7
1 0
0 -1

예제 출력 2

-1

예제 입력 3

5 7 10
-1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 0 -1 -1
-1 -1 0 1 0 -1 -1
-1 -1 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1

예제 출력 3

1
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 1 0 1 1
0 0 0 0 0 0 0
1 1 1 1 1 1 1

노트

부분 직사각형이란, 행을 위부터 1, 2, …, N으로 번호를 매기고 열을 왼쪽부터 1, 2, …, M으로 번호를 매길 때, 1 r1 r2  N, 1 c1 c2 M인 어떤 r1, r2, c1, c2에 대하여 행의 번호가 r1 이상 r2 이하이며, 열의 번호가 c1 이상 c2 이하인 모든 칸의 집합을 뜻한다. 가능한 모든 부분 직사각형이란, 부등식을 만족하는 모든 서로 다른 (r1,c1,r2,c2)에 대해 한 번씩 직사각형을 만든 것을 뜻한다.