== include(page="template/taskheader" task_id="transform2") ==

Poveste şi cerinţă...

O matrice pătratică de dimensiuni $N x N$ cu liniile şi coloanele indexate de la $1$ la $N$ se numeşte *matrice şmecheră de Calafat* dacă pe fiecare linie şi fiecare coloană există exact două valori de $1$, restul elementelor fiind $0$.
 
h2. Cerinta
 
Având două *matrice şmechere de Calafat* notate cu $A$ şi $B$, se cere ca prin interschimbări de linii şi coloane să se transforme matricea $B$ în matricea $A$.

h2. Date de intrare

Fişierul de intrare $transform2.in$ ...

Fişierul $transform2.in$ conţine pe prima linie numărul $N$, reprezentând dimensiunea matricei. Pe următoarele $2N$ linii avem câte o pereche de numere naturale separate prin spaţiu, reprezentând linia şi coloana unui element de valoare $1$ din matricea $A$. În continuare pe următoarele $2N$ linii avem câte o pereche de numere naturale separate prin spaţiu, reprezentând linia şi coloana unui element de valoare $1$ din matricea $B$.

h2. Date de ieşire

În fişierul de ieşire $transform2.out$ ...

Fişierul $transform2.out$ va conţine pe fiecare linie câte o operaţie de interschimbare a două linii sau două coloane, codificată printr-un triplet $ch x y$ format dintr-un caracter $ch$ şi două numere naturale $x$ şi $y$ separate prin câte un spaţiu. Valoarea lui $ch$ de fiecare dată poate fi doar $’L’$ , $’C’$ sau $’0’$. Dacă valoarea lui $ch$ este egală cu $’L’$, atunci se vor interschimba liniile $x$ şi $y$ în matricea $B$. Dacă valoarea lui $ch$ este egală cu $’C’$, atunci se vor interschimba coloanele $x$ şi $y$ în matricea $B$. Ultimul triplet de valori introdus în fişierul de ieşire va fi $’0 0 0’$ reprezentând terminarea acţiunii.

h2. Restricţii

* $... ≤ ... ≤ ...$
 

* $1 ≤ N ≤ 80000$
* Pentru un program care se încadrează în timpul de execuţie, punctajul acordat depinde de numărul de operaţii tipărite în fişierul de ieşire. Să notăm cu op numărul de operaţii efectuate. Astfel pentru fiecare fişier de ieşire corect, punctajul se va acorda astfel:
o dacă $1 ≤ op ≤ 2N$, se acordă $100%$ din punctaj;
o dacă 2N+1  op  4N , se acordă $75%$ din punctaj;
o dacă op > 4N, se acordă 50% din punctaj.
 Pentru toate testele de intrare există soluţie.

h2. Exemplu
table(example). |_. transform2.in |_. transform2.out |