타일 퍼즐

당신은 고대 현대 박물관에 방문했다. 오늘은 자연과학의 역사에 관한 전시회가 열린다. 고대, 중세, 현대의 과학과 수학에 관한 흥미로운 전시물을 많이 보고, 지금은 휴게 공간에 있다.

그곳에서 여러 개의 패널을 발견했다. 각 패널에는 정사각 격자로 배열된 N × N 개의 전기 타일이 있다. 각 타일은 다음 색 중 하나로 켜진다: 검정(꺼짐), 빨강, 초록, 노랑, 파랑, 자홍, 청록. 처음에는 모든 타일이 검정이다. 타일을 한 번 누르면 그 타일과 인접한 여덟 타일의 색이 다음과 같이 바뀐다: 검정 -> 빨강, 빨강 -> 초록, 초록 -> 노랑, 노랑 -> 파랑, 파랑 -> 자홍, 자홍 -> 청록, 청록 -> 검정. 여기서 가장 왼쪽 열과 가장 오른쪽 열은 인접한 것으로 간주하고, 가장 위쪽 행과 가장 아래쪽 행도 마찬가지다. 각 패널에는 목표 패턴이 있으며, 목표 패턴에 제시된 대로 타일의 색을 바꾸어야 한다. 예를 들어 4 × 4 패널에 대해 아래 그림과 같은 목표 패턴이 주어지면, 왼쪽 위 타일을 한 번 누르고 오른쪽 아래 타일을 두 번 누르면 된다(이것이 유일한 방법은 아닐 수 있다).

당신은 프로그래밍을 잘하므로 컴퓨터로 답을 찾을 수 있다고 생각한다. 따라서 이 문제에서 당신의 일은 그 프로그램을 작성하는 것이다.

그림 1: 목표 패턴 예시

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다:

N
Row1
...
RowN

N 은 전기 패널의 크기, 즉 행과 열의 개수이다(3 ≤ N ≤ 15). Rowi 는 i 번째 행의 목표 패턴을 나타내며, 공백으로 구분된 정확히 N 개의 숫자를 포함한다. j 번째 숫자는 j 번째 열의 색을 나타내며, 다음 중 하나이다: 0(검정), 1(빨강), 2(초록), 3(노랑), 4(파랑), 5(자홍), 6(청록).

입력은 0 하나만 있는 줄로 끝난다. 이 줄은 어떤 데이터셋에도 속하지 않는다.

각 데이터셋에 대해 프로그램은 N 개의 줄을 출력해야 한다. i 번째 줄은 i 번째 행에 대응하며, 공백으로 구분된 정확히 N 개의 숫자를 포함한다. j 번째 숫자는 j 번째 열 타일을 누른 횟수이다. 이 숫자는 0 이상 6 이하이다.

답이 여러 개면 그중 아무거나 출력해도 된다. 목표 패턴을 만들 수 없으면, N 개의 줄 대신 “-1”(따옴표 제외) 한 줄을 출력해야 한다.

각 데이터셋의 출력 뒤에는 빈 줄이 하나 있어야 한다(마지막 데이터셋의 출력 뒤에도 마찬가지이다).