Problem 1415: amestec

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 $d_i$ ( $1 \leq i \leq K$ ) exprimată în secunde
poziția aplicării forței, notată cu $p_i$ {‘N’, ‘S’, ‘E’, ‘V’}, $1 \leq i \leq 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 $m_i$ , $1 \leq i \leq 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 din 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 $d_i$ , un caracter $p_i$ (’N’,’S’,’E’,’V’) și un număr natural $m_i$ , $1 \leq i \leq 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 din 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 și precizări

$2 \leq N \leq 100$
$1 \leq K \leq 100$
$1 \leq d_i \leq 10^9, 1 \leq i \leq K$

Exemplu

amestec.in

amestec.out

111
110
100

Explicație

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

amestec