Bulbs Solution Tests

A rectangular publicity panel contains bulbs organized in rows and columns.

Each row and each column have a switch, which changes the status of every bulb from its initial state into the contrary state (on/off, off/on). You can not switch bulbs one by one. Initially, the panel has all the bulbs off.

Task

Write a program that transforms the panel from the original configuration to a given configuration, switching a minimum number of rows and columns, if that is possible.

Input format

The input file BECURI.IN contains:

Output format

A solution will be printed in the output file BECURI.OUT:

If the row or column is not switched, print 0 on the corresponding line.

The numbering of the lines and columns starts from 1.

If the problem has no solutions, print on the first line of the file –1.

Constraints:

Example:

BECURI.IN

 

BECURI.OUT

5 6

1 0 1 1 0 1

1 0 1 1 0 1

1 0 1 1 0 1

0 1 0 0 1 0

0 1 0 0 1 0

 

2 5

1 2 3

Time limit: 1 second/test.