오류 정정

불리언 행렬이 패리티 성질(parity property) 을 가진다는 것은 모든 행과 모든 열의 합이 짝수, 즉 켜져 있는 비트(값이 1인 칸)의 개수가 짝수라는 뜻이다. 다음은 패리티 성질을 가지는 4 × 4 행렬의 예이다.

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

각 행의 합은 2, 0, 4, 2이고, 각 열의 합은 2, 2, 2, 2이다.

행렬을 읽어 패리티 성질을 가지는지 판별하는 프로그램을 작성하라. 가지지 않는다면 단 하나의 비트만 바꾸어 패리티 성질을 만들 수 있는지 확인한다. 그것도 불가능하다면 그 행렬은 손상됨(corrupt) 으로 분류한다.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 행렬의 크기를 나타내는 정수 n (n < 100)이 주어진다. 이어지는 n 개의 줄에는 한 줄마다 n 개의 정수가 주어진다. 행렬에는 0과 1 이외의 값은 나타나지 않는다. 입력은 n 이 0인 값으로 종료된다.

입력의 각 행렬에 대해 한 줄씩 출력한다. 행렬이 이미 패리티 성질을 가지고 있으면 OK를 출력한다. 하나의 비트를 바꾸어 패리티 성질을 만들 수 있으면 Change bit (i,j)를 출력하는데, i 는 바꿀 비트의 행, j 는 열이다(행과 열은 1부터 센다). 그 외의 경우에는 Corrupt를 출력한다.