Se consideră un amestec de două substanţe, ale căror molecule se notează cu 0, respectiv 1, reprezentat ca o matrice pătratică cu n linii şi n coloane.
În vederea separării celor două substanţe, asupra amestecului se aplică succesiv o serie de k forţe magnetice, caracterizate de următoarele trei mărimi:
• durata aplicării forţei, notată cu di (1 ≤ i ≤ k) exprimată în secunde;
• poziţia aplicării forţei, notată cu pi din {’N’,’S’,’E’,’V’}, 1 ≤ i ≤ k, ce reprezintă unul dintre cele patru puncte cardinale (Nord, Sud, Est, Vest);
• tipul moleculelor (0 sau 1) asupra cărora acţionează forţa, notat cu mi, 1 ≤ i ≤ k.
Deplasarea moleculelor se face după următoarele reguli:
• moleculele se deplasează numai pe orizontală când forţa este aplicată în Est sau Vest sau numai pe verticală când forţa este aplicată în Nord sau Sud;
• moleculele se deplasează către locul în care este amplasată forţa şi, într-o secundă, o moleculă se deplasează cel mult cu o singură poziţie;
• o moleculă se deplasează numai dacă în faţa ei, în direcţia de deplasare, există o moleculă de alt tip, cu care face schimb de locuri, altfel rămâne pe aceeaşi poziţie;
• o forţă acţionează asupra tuturor moleculelor de tipul precizat.
Cerinţă
Să se scrie un program care determină matricea amestecului obţinut după aplicarea forţelor magnetice.
Spre exemplu, dacă n=3, matricea moleculelor este cea de mai jos şi se aplică k=2 forţe, caracterizate prin 1N1, 2E0, amestecul va trece prin următoarele etape:
Date de intrare
Fişierul de intrare amestec.in conţine pe prima linie două numerele naturale, n şi k, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele n linii se găseşte câte un şir de n caractere 0 sau 1. Pe fiecare dintre următoarele k linii se găsesc câte 3 valori, după cum urmează: un număr natural di, un caracter pi din {’N’,’S’,’E’,’V’} şi un număr natural mi, 1 ≤ i ≤ k, având semnificaţia de mai sus, neseparate prin spaţiu.
Date de ieşire
Fişierul de ieşire amestec.out va conţine matricea amestecului final. Pe fiecare dintre cele n linii ale fişierului de ieşire se va scrie câte un şir de n caractere 0 sau 1, neseparate prin spaţiu.
Restricţii
• 2 ≤ n ≤ 100
• 1 ≤ k ≤ 100
• 1 ≤ di ≤ 109 , 1 ≤ i ≤ k
Exemple
amestec.in
amestec.out
Explicaţii
3 2
011
101
110
1N1
2E0
111
110
100
Matricea moleculelor are 3 linii şi 3 coloane.
Se aplică un număr de k=2 forţe, prima cu durata de 1 secundă, spre nord, și care atrage moleculele de tip 1, și a doua cu durata de 2 secunde, spre est, ce atrage moleculele de tip 0. După aplicarea celor 2 forțe, moleculele se vor reașeza conform matricei alăturate.
