Se consideră un tablou cu N linii şi N coloane (numerotate de la 1 la N) care conţine valoarea 1 în fiecare dintre cele NxN celule. Valorile din tablou pot fi modificate prin aplicarea a două operații codificate astfel:

• L nr, prin care se schimbă simultan toate semnele numerelor din linia cu numărul nr.
• C nr, prin care se schimbă simultan toate semnele numerelor din coloana cu numărul nr.

Cerințe

1) Dându-se o succesiune de K operații (L nr sau C nr) asupra liniilor/coloanelor tabloului inițial (în care toate celulele conțin valoarea 1) să se determine numărul valorilor pozitive din tablou la finalul executării celor K operații.
2) Să se determine numărul minim de operații L nr sau C nr, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z valori negative.

Date de intrare

Fișierul de intrare tablou.in conține pe prima linie numărul p=1 sau p=2, reprezentând numărul cerinței ce trebuie rezolvată.

• Dacă p=1 atunci linia a doua a fișierului de intrare conține numerele N și K, separate printr-un spațiu, iar următoarele K linii conțin fiecare câte o literă mare (L sau C) și un număr nr, separate printr-un spațiu, reprezentând codificarea uneia dintre cele două operații (L nr sau C nr).
• Dacă p=2 atunci linia a doua a fișierului de intrare conține numerele N și Z, separate printr-un spațiu.

Date de ieșire

• Dacă p=1, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural, reprezentând numărul valorilor pozitive din tabloul obținut la finalul executării celor K operații asupra tabloului inițial (răspunsul la cerința 1).
• Dacă p=2, atunci fișierul de ieșire tablou.out conține pe prima linie un număr natural reprezentând numărul minim de operații L nr sau C nr, care, aplicate tabloului inițial, îl modifică astfel încât tabloul obținut să conțină exact Z valori negative (răspunsul la cerința 2). Dacă prin aplicarea de operații L nr sau C nr tabloului inițial nu se poate obține un tablou cu Z valori negative, atunci, fișierul va conține pe prima linie valoarea 0 (zero).

Restricții și precizări

• N, K, Z și nr sunt numere naturale
• 3 ≤ N ≤ 20000; 1 ≤ K ≤ 43000; 1 ≤ Z ≤ N*N; 1 ≤ nr ≤ N
• Prin schimbare de semn, valoarea -1 se transformă în 1 și valoarea 1 se transformă în -1
• În concurs s-au acordat 10 puncte din oficiu și câte 45 puncte pentru rezolvarea corectă a fiecărei cerințe. Pe site se acordă 10 puncte pentru rezolvarea corectă a exemplelor.

Exemplul 1

tablou.in

1
4 4
L 1
L 3
C 1
L 1

tablou.out

10

Explicație

N=4. La finalul aplicării succesiunii de K=4 operații, tablou modificat are conținutul:

-1  1  1  1
-1  1  1  1
 1 -1 -1 -1
-1  1  1  1  

Astfel, tabloul conține 10 valori pozitive.

Exemplul 2

tablou.in

2
3 5

tablou.out

3

Explicație

Sunt necesare minimum 3 operații, de exemplu: L 3, L 1, C 1

Exemplul 3

tablou.in

2
4 7

tablou.out

0

Explicație

Nu există nicio succesiune de operații pentru care să se obțină Z=7 valori negative.