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: