matrice

Se dau $N$ şi $M$ două numere naturale şi o matrice $A$ cu $N$ linii (numerotate de la $1$ la $N$) şi $M$ coloane (numerotate de la $1$ la $M$) având elementele numere întregi în intervalul închis $[-30 \ 000, 30 \ 000]$. Asupra acestei matrice se pot efectua mai multe operaţii de ştergere a unor linii, de ordonare a elementelor aflate pe anumite linii sau de adăugare a unor noi linii la sfârşitul matricei. Fiecare dintre aceste operaţii este codificată printr-o comandă având următoarea sintaxă:

Ştergerea este precizată printr-o linie de forma: $S \ i \ j \ k \ i_1 \ o_1 \ v_1 \ i_2 \ o_2 \ v_2 \ i_3 \ o_3 \ v_3 \dots i_k \ o_k \ v_k$

Comanda precizează că se şterg din matrice acele linii $L \in \{i, i+1, i+2, \dots, j \}$ pentru care sunt îndeplinite simultan următoarele condiţii:

• $A_{L \ i_1}$ este în relaţia $o_1$ faţă de $v_1$
• $A_{L \ i_2}$ este în relaţia $o_2$ faţă de $v_2$
• $\dots$
• $A_{L \ i_k}$ este în relaţia $o_k$ faţă de $v_k$

unde $o_1$, $o_2$, $\dots$, $o_k$ pot fi unul dintre operatorii < (mai mic), > (mai mare), ! (diferit), = (egal).

De exemplu comanda: $S \ 3 \ 5 \ 2 \ 2 < 10 \ 5 \ ! \ 7$ precizează că se şterg liniile $L \in \{3, 4, 5 \}$ în cazul în care $A_{L \ 2} < 10$ şi $A_{L \ 5} \neq 7$.

După ştergerea tuturor liniilor precizate se va proceda la renumerotarea liniilor din matrice, iar dimensiunea matricii se va modifica.

Ordonarea este precizată printr-o linie de forma $O \ i \ j \ t \ col_1 \ ch_1 \ col_2 \ ch_2 \ col_3 \ ch_3 \dots col_t \ ch_t$ cu semnificaţia că liniile $i, i+1, i+2, \dots, j$ sunt sortate după valoarea din coloana $col_1$, dacă pentru două linii valoarea din coloana $col_1$ coincide se vor ordona după coloana $col_2$, apoi după coloana $col_3$ etc. Sortarea după o anumită coloană $col_i$ se face crescător dacă $ch_i$ este C respectiv descrescător dacă $ch_i$ este D. Dacă două linii conţin valori identice în toate cele $t$ coloane, se va păstra ordinea relativă în care apar ele în tabela iniţială.

Adăugarea este precizată printr-o linie de forma $A \ v_1 \ v_2 \dots v_M$ cu semnificaţia că se adaugă la sfârşitul matricei, după ultima sa linie, o linie nouă, elementele noii linii având pe rând, de la stânga la dreapta, valorile $v_1 \ v_2 \dots v_M$.

Cerinţă

Scrieţi un program care citeşte elementele matricei iniţiale, apoi citeşte un şir de comenzi şi determină matricea rezultată după efectuarea operaţiilor precizate prin comenzile respective în ordinea în care acestea sunt date.

Date de intrare

Fişierul de intrare matrice.in conţine pe prima linie numerele naturale $N$ şi $M$ separate printr-un spaţiu. Pe fiecare dintre următoarele $N$ linii se află câte $M$ numere întregi, reprezentând elementele matricei. Elementele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Următoarea linie a fişierului de intrare conţine un singur număr natural $P$, reprezentând numărul de operaţii ce se aplică matricei. Următoarele $P$ linii ale matricei precizează fiecare câte o comandă care se aplică matricei, respectând sintaxa şi precizările din enunţ.

Date de ieșire

Fişierul de ieşire matrice.out va conţine pe prima linie un număr natural $R$ reprezentând numărul de linii al matricei finale. Pe fiecare dintre următoarele $R$ linii se află câte $M$ numere întregi, reprezentând elementele matricei finale. Elementele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Restricții și precizări

• $1 \leq N, R \leq 200$
• $1 \leq M \leq 100$
• $1 \leq P \leq 150$
• Niciuna dintre matricele intermediare nu au mai mult de $200$ de linii
• Numărul maxim de condiţii pentru orice comandă de ştergere sau de ordonare este de $20$ ($1 \leq k, t \leq 20$)
• Toate comenzile din fişierul de intrare sunt corecte atât din punct de vedere sintactic dar şi din punct de vedere logic, adică nu se cere de exemplu sortarea sau ştergerea unor linii din afara matricei.

Exemplu

matrice.in

10 4
5 1 6 3
4 2 3 7
4 2 3 2
2 8 1 3
4 2 1 6
1 3 2 1
9 7 5 1
9 7 3 8
3 8 2 6
6 7 1 3
8
O 2 5 1 3 C
O 7 10 1 2 C
S 5 9 1 1 < 4
A 7 3 5 1
A 9 2 1 6
O 2 7 3 2 C 1 D 4 D
O 1 11 1 3 C
S 1 11 2 1 > 4 3 ! 5

matrice.out

7
4 2 1 6
2 8 1 3
3 8 2 6
4 2 3 7
4 2 3 2
9 7 5 1
7 3 5 1