seif

Seiful SEPI, în care sunt depozitate premiile olimpiadelor de informatică, este securizat cu un cifru sub forma unei matrice $A$ de formă pătratică cu $N$ linii și $N$ coloane, unde $N$ este un număr natural par. Liniile și coloanele sunt numerotate începând cu $1$.

Matricea-cifru $A$ este formată din $\frac{N}{2}$ chenare. Al $i$-lea chenar ($1 \leq i \leq \frac{N}{2}$) va conține elementele aflate pe marginea matricei $A$, după excluderea primelor $i - 1$ chenare. Ordinea elementelor acestui chenar este obținută pornind din poziția $(i, i)$, parcurgând latura de sus de la stânga la dreapta, latura din dreapta de sus în jos, latura de jos de la dreapta la stânga și apoi latura din stânga de jos în sus.

De exemplu, pentru $N = 4$ și matricea-cifru din figura alăturată, elementele primului chenar sunt, în ordinea parcurgerii, $7, 4, 5, 6, 8, 7, 9, 5, 4, 3, 1, 5$ (colorate cu gri deschis).
Elementele celui de al doilea chenar se află pe marginea matricei $A$, după excluderea primului chenar. Elementele de pe al doilea chenar, în ordinea parcurgerii lor, sunt $7, 9, 4, 2$ (colorate cu gri închis).

Fiecare chenar acționează ca un rotor al cifrului și elementele sale pot fi permutate circular către stânga sau către dreapta cu un anumit număr de poziții.
Asupra matricei-cifru se aplică o succesiune de $T$ de operații de permutare circulară a elementelor unui chenar dat cu un număr oarecare de poziții, către stânga sau către dreapta.

O operație de permutare circulară are următoarea structură: chenar pozitii sens, unde $chenar$ reprezintă numărul de ordine al chenarului asupra căruia se aplică permutarea, $pozitii$ reprezintă numărul de poziții cu care se permută, iar $sens$ este un caracter: S pentru stânga sau D pentru dreapta.

Cerință

Cunoscând numărul natural $N$, cele $N \cdot N$ elemente ale matricei-cifru precum și succesiunea de $T$ operații de permutare circulară a unor chenare, să se determine configurația finală a matricei, cea care va permite deschiderea seifului!

Date de intrare

Fișierul de intrare seif.in conține:

• pe prima linie numărul natural $N$
• pe fiecare dintre următoarele $N$ linii, câte $N$ numere naturale reprezentând matricea-cifru inițială
• pe linia $N + 2$ numărul natural $T$ reprezentând numărul de operații de permutare
• pe următoarele $T$ linii sunt scrise cele $T$ operații de permutare circulară, câte o operație pe fiecare linie, în formatul descris în enunț: chenar pozitii sens.

Date de ieșire

Fișierul de ieșire seif.out va conține pe primele $N$ linii câte $N$ numere reprezentând elementele matricei după aplicarea celor $T$ operații de permutare circulară.

Restricții și precizări

• $2 \leq N \leq 500$
• $N$ este număr par
• $1 \leq T \leq 10^5$
• Numărul de poziții cu care se face o permutare este nenul și $\leq 10^6$.
• Elementele matricei-cifru sunt numere naturale $\leq 2 \cdot 10^9$.
• Pe un chenar se pot face mai multe operații de permutare circulară.
• Elementele scrise pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate prin câte un singur spațiu.

Exemplul 1

seif.in

2
1 2
4 3
3
1 1 D
1 3 S
1 3 D

seif.out

4 1 
3 2

Explicație

$N = 2$ și $T = 3$. Matricea se modifică după cum urmează:

inițial:

1 2
4 3

după operația $1 \ 1 \ D$:

4 1
3 2

după operația $1 \ 3 \ S$:

3 4
2 1

după operația $1 \ 3 \ D$:

4 1
3 2

Exemplul 2

seif.in

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

seif.out

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

Explicație

$N = 4$ și $T = 2$. Matricea se modifică după cum urmează:

inițial

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

după operația $1 \ 1 \ D$:

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

după operația $2 \ 5 \ S$:

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