Luci al Pirellone

Il Pirellone è un noto grattacielo di Milano, in cui le finestre sono disposte ordinatamente per N righe (piani) e M colonne.
Le righe sono numerate da 1 a N (dall’alto in basso) e le colonne da 1 a M (da sinistra a destra).

Non tutti i dipendenti spengono la luce dei loro uffici, la sera prima di uscire.
Quindi alcune finestre rimangono illuminate e tocca al custode provvedere a spegnerle.

Per facilitare il compito del custode, sono stati predisposti N+M interruttori speciali, con un funzionamento particolare.
Ci sono N interruttori di riga e M interruttori di colonna.
Quando il custode agisce sull’i-esimo interruttore di riga, tutte le luci accese dell’i-esima riga si spengono ma, allo stesso tempo, quelle spente si accendono!
Analogamente alle righe, un interruttore di colonna spegne le luci accese di quella colonna e accende quelle spente.

Aiuta il custode a decidere quali degli N+M interruttori azionare al fine di spegnere tutte le luci delle finestre del Pirellone.
Data la configurazione iniziale di luci, il custode deve verificare se sia possibile spegnere le luci con gli interruttori speciali e, in tal caso, deve specificare anche su quali interruttori agire.
Altrimenti, stabilisce che è necessario utilizzare gli interruttori tradizionali.

Dati in Input

Il file input.txt contiene nella prima riga gli interi N e M, ovvero il numero di righe e di colonne del Pirellone, rispettivamente.

Ognuna delle successive N righe contiene una sequenza di M valori 0 oppure 1, separati da uno spazio.
La sequenza contenuta nell’i-esima di tale righe rappresenta lo stato delle luci nell’i-esima riga (piano) del Pirellone.
In particolare, il j-esimo valore in tale riga indica se la j-esima luce è accesa (valore = 1) oppure spenta (valore = 0).

Dati in Output

Il file output.txt deve contenere due linee per indicare su quali interruttori deve agire il custode.

La prima linea contiene una sequenza di N valori (0 oppure 1) separati da uno spazio, per rappresentare le operazioni che il custode deve effettuare sugli interruttori di riga.
L’i-esimo valore della sequenza indica se il custode deve agire sull’interruttore dell’i-esima riga (valore = 1) oppure no (valore = 0).

Analogamente, la seconda linea contiene una sequenza di M valori (0 oppure 1) separati da uno spazio, per rappresentare le operazioni che il custode deve effettuare sugli interruttori di colonna.
Il j-esimo valore della sequenza indica se il custode deve agire sull’interruttore della j-esima colonna oppure no.

Nel caso in cui non sia possibile spegnere tutte le luci del Pirellone con gli interruttori speciali, tutti i valori delle due linee inoutput.txt devono essere uguali a 0.

Assunzioni

• 1 < N < 500
• 1 < M < 500
• Il Pirellone ha almeno una luce accesa.

Esempi