Error Correction

A boolean matrix has the parity property when each row and each column has an even sum, i.e. it contains an even number of bits that are set. Here is a 4 × 4 matrix that has the parity property:

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

The sums of the rows are 2, 0, 4, and 2. The sums of the columns are 2, 2, 2, and 2.

Write a program that reads in a matrix and checks whether it has the parity property. If it does not, the program should check whether the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt.

The input contains one or more test cases. The first line of each test case contains one integer n (n < 100), the size of the matrix. Each of the next n lines contains n integers. No integers other than 0 and 1 occur in the matrix. The input is terminated by a value of 0 for n.

For each matrix in the input, print one line. If the matrix already has the parity property, print OK. If the parity property can be established by changing one bit, print Change bit (i,j), where i is the row and j the column of the bit to be changed (rows and columns are numbered from 1). Otherwise, print Corrupt.