Internet Problem Solving Contest

IPSC 1999

Problem F – Panel

Bulbville is a small town. However, its main square resembles a scene from Las Vegas. It is full of colorful blinking pipes and panels advertising various local companies. Nevertheless, a particular influential family residing at the main square has started to complain that a certain advertising panel shines into the windows of their residence. Therefore, they demand that the panel be switched off during the night.

The panel is a square consisting of N rows of bulbs with N bulbs in each row. However, it has only 2N switches - one for each row and one for each column. The switch for a given row (or a column) turns off all the bulbs in a given row (or a column) which are on and turns on all the bulbs which are off. It might not be possible to turn off all the bulbs of the panel. Your task is to determine a configuration of the panel with the least number of shining bulbs that can be achieved using the switches.

Input specification.

The input describes the initial configuration of the advertising panel. The first line consists of a single number N. Each of the next N lines describes one row of the panel starting from the top. It contains N numbers separated by spaces - each number standing for one bulb, 1 if the bulb is on, 0 if the bulb is off, starting from the left.

Output specification.

The first line of the output contains one integer M, giving the minimum number of shining bulbs. The next N lines describe one of possible minimum final configurations in the same format as was the initial configuration in the input described. To prevent the problems with the mailer you may split long lines into several shorter ones.


Input file:
1 0 1 1                      
1 0 1 0                      
1 1 1 0                      
0 1 0 0                      
Output file:
0 0 0 0
0 0 0 1
0 1 0 1
0 0 0 0