transform

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.

Cerință

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.

Date de intrare

Fișierul transform.in conține pe prima linie numărul N, reprezentând dimensiunea matricii. 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.

Date de ieșire

Fișierul transform.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.

Restricții și precizări

• 1 ≤ N ≤ 80 000
• 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:
• dacă 1 ≤ op ≤ 2N , se acordă 100% din punctaj;
• dacă 2N+1 ≤ op ≤ 4N , se acordă 75% din punctaj;
• dacă op > 4N, se acordă 50% din punctaj.
• Pentru toate testele de intrare există soluție.

Exemplu

transform.in

4
1 1
2 2
3 3
4 1
3 4
4 4
2 3
1 2
1 3
2 3
1 1
2 2
4 2
4 4
3 4
3 1

transform.out

L 3 4
C 3 2
0 0 0

Explicație

N=4
Prima dată se citește matricea A:

1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1

apoi citim matricea B:

1 0 1 0
0 1 1 0
1 0 0 1
0 1 0 1

Aplicăm operația L 3 4 interschimbând liniile 3 și 4 în matricea B:
1 0 1 0
0 1 1 0
0 1 0 1
1 0 0 1

Aplicăm operația C 3 2 interschimbând coloanele 3 și 2 în matricea B:
1 1 0 0
0 1 1 0
0 0 1 1
1 0 0 1

Citind linia 0 0 0 înțelegem că s-au terminat operațiile și s-a obținut matricea A.