PANEL - Panel

no tags 

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(N<=50). 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 and the only line of the output contains one integer M, giving the minimum number of shining bulbs. N lines follow, each contains a single integer 1 or 0 denoting whether you wants to use the switch for the i-th row. N lines follow, each contains a single integer 1 or 0 denoting whether you wants to use the switch for the i-th column.

Example

Input file:
4
1 0 1 1
1 0 1 0
1 1 1 0
0 1 0 0

Output file:
3
0
0
0
1
1
0
1
1


Added by:Fudan University Problem Setters
Date:2007-12-01
Time limit:0.135s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO OBJC SQLITE
Resource:IPSC 1999