#361 멋없는 격자

Statement

問題文の言語

$N$ 행 $M$ 열의 격자 $A$ 가 주어진다. 각 칸에는 $0$ 또는 $1$ 이 적혀 있다.

$(1,1)$ 에서 $(N,M)$ 으로 가는 최단 경로는 매 이동마다 오른쪽 또는 아래쪽으로 한 칸 이동한다. 경로가 방문하는 칸의 문자를 시작 칸부터 도착 칸까지 순서대로 읽어 길이 $N+M-1$ 의 이진 문자열을 만든다.

서로 다른 두 최단 경로가 같은 이진 문자열을 만들 수 있으면 이 격자를 멋있는 격자라고 한다. 그렇지 않으면, 즉 모든 최단 경로가 서로 다른 이진 문자열을 만들면 이 격자는 멋있는 격자가 아니다.

서로 다른 정확히 $K$ 개의 칸을 골라 각 칸의 값을 한 번씩 반전시키려고 한다. $0$ 은 $1$ 로, $1$ 은 $0$ 으로 바뀐다.

정확히 $K$ 개의 칸을 반전시킨 뒤 멋있는 격자가 아닌 격자를 하나 만들어 출력하여라. 그런 격자를 만들 수 없다면 불가능함을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N\ M\ K$ $A_1$ $A_2$ $\vdots$ $A_N$

$A_i$ 는 길이 $M$ 의 이진 문자열이며, $j$ 번째 문자는 $(i,j)$ 칸의 값을 나타낸다.

각 테스트 케이스마다 답을 출력한다.

조건을 만족하는 격자를 만들 수 없다면 한 줄에 -1을 출력한다.

만들 수 있다면 $N$ 개의 줄에 길이 $M$ 의 이진 문자열을 출력한다. 출력한 격자는 원래 격자와 정확히 $K$ 개의 칸에서 달라야 하며, 멋있는 격자가 아니어야 한다.

가능한 답이 여러 가지라면 아무거나 출력해도 된다.

#	得点	制約
1	8	$\min(N,M)=1$ .
2	14	모든 $A_{i,j}$ 가 $0$ 이다.
3	18	$N,M\leq6$ . 모든 테스트 케이스에 대한 $NM$ 의 합은 $400$ 이하이다.
4	15	$K=0$ .
5	45	추가적인 제약이 없다.

入力例

出力例

두 번째 테스트 케이스에서는 $(1,2)$ 의 값을 반전시키면 정확히 한 칸이 바뀐다. 세 번째 테스트 케이스는 최단 경로가 하나뿐이므로 출력한 격자도 조건을 만족한다.