cap-pajura

Monedele vechi aveau imprimate pe una dintre fețe figura regelui ("cap"), iar pe cealaltă un însemn al țării care a emis moneda ("pajura").
Atunci când arbitrul cere căpitanilor de echipă să aleagă jumătatea de teren pe care vor începe jocul, el aruncă în aer o monedă. Aceasta cade pe pământ cu una dintre fețe în sus, "capul" sau "pajura". Căpitanul de echipă care a ales fața de sus este cel care alege terenul.
Să presupunem că, în urma aruncării în sus a mai multor monede, acestea cad pe pământ într-o configurație de nxm monede (adica sub forma unei matrice cu n linii si m coloane), unele având "capul" pe fața de sus, altele având "pajura". Arbitrul nostru, iubitor de probleme, dorește să obțină toate monedele cu pajura în sus. Pentru aceasta el restricționează operațiile posibile doar la două:
- o întreagă linie este "inversată";
- o întreagă coloană este "inversată".
Prin "inversarea" unei linii/coloane fiecare monedă de pe linia/coloana respectivă este inversată.

Cerință
Date dimensiunile configurației n și m, precum și configurația monedelor, să se determine dacă, folosind numai cele două operații permise, se poate transforma configurația inițială astfel încât, la final, toate monedele să fie cu "pajura" în sus.

Date de intrare
Fișierul de intrare pajura.in conține mai multe seturi de date. Un set de date conține pe prima linie valorile n și m separate printr-un spațiu. Următoarele n linii din setul de date conțin câte m caractere C sau P, fără spații între ele, reprezentând configurația inițială a monedelor. Seturile de date se termină cu două valori 0 separate printr-un spațiu.

Date de ieșire
Dacă în fișierul de intrare au fost k seturi de date, atunci fișierul de ieșire pajura.out va avea k linii, pe fiecare linie fiind scrisă una dintre valorile 1 sau 0, după cum configurația inițială poate fi transformată sau nu.

Restricții și precizări
1 <= n, m <= 1000
Numarul de seturi de date din orice fisier de intrare este <=10.

Exemplu

pajura.in pajura.out Explicatii

3 4
CPCC
PCPP
CPCC
5 2
PC
CC
CP
CC
CC
0 0

 1
0
 Fișierul de intrare conține 2 seturi de date.
Pentru primul set de date o posibilă succesiune de operații este:

CPCC  coloana 2 CCCC   linia 1   PPPP    linia 3  PPPP
PCPP ---------> PPPP ----------> PPPP ----------> PPPP
CPCC            CCCC             CCCC             PPPP

Pentru cel de-al doilea set de date, nici o succesiune de operații nu conduce la un rezultat favorabil.

Timp maxim de execuție/test: 0.2 secunde

prof. Marinel Șerban
Liceul de Informatică "Gr. C. Moisil" Iași
marinel_serban@yahoo.com