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 [-30000,30000]. 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] ... i[k] o[k] v[k]

Comanda precizează că se şterg din matrice acele linii L din mulțimea {i, i+1, i+2, ..., 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]
• …
• A[L][i[k]] este în relaţia o[k] faţă de v[k]

unde o[1], o[2], …, 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 din {3, 4, 5} în cazul în care A[L][2]<10 și A[L][5]≠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] ... col[t] ch[t]

cu semnificaţia că liniile i, i+1, i+2, ..., 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] ... 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], …, v[M].

Cerința

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 matrice2.in conține pe prima linie numerele naturale N şi M separate printr-un spaţiu. Pe fiecare dintre următoarele N linii se afla 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 matrice2.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 ≤ N, R ≤ 200
• 1 ≤ M ≤ 100
• 1 ≤ P ≤ 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 ≤ k,t ≤ 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:

matrice2.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

matrice2.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