Problem 107: matrice

Se dă o matrice cu $N$ linii și $2$ coloane de numere întregi. Liniile sunt numerotate cu numere de la $1$ la $N$ , iar coloanele cu $1$ și $2$ .

Există $4$ operații care pot fi executate asupra matricii: $S_3, J_3, S_4, J_4$ .

La o operație $J_k$ se aleg $k$ linii (distincte) ale matricii și se permută circular în jos, iar la o operație $S_k$ se aleg $k$ linii (distincte) și se permută circular în sus ( $k=3,4$ ).

\begin{vmatrix} \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ \end{vmatrix} \rightarrow \begin{vmatrix} \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ \end{vmatrix} \\

\text{Operație } J_3

\begin{vmatrix} \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ \end{vmatrix} \rightarrow \begin{vmatrix} \cdots & \cdots \\ y_1 & y_2 \\ \cdots & \cdots \\ z_1 & z_2 \\ \cdots & \cdots \\ x_1 & x_2 \\ \cdots & \cdots \\ \end{vmatrix} \\

\text{Operație } S_3

Operațiile $S_4$ si $J_4$ sunt similare, numai că în loc de $3$ linii se aleg $4$ .

Cerința

Scrieți un program care prin efectuarea a cel mult $2N$ operații de tip $S_3, J_3, S_4, J_4$ asupra matricii date să o transforme astfel încât nici una dintre coloanele ei să nu conțină un subșir strict crescător de lungime mai mare decât $\lceil \sqrt{N} \rceil$ (adică cel mai mic întreg mai mare sau egal decât $\sqrt{N}$ ).

Date de intrare

Fișierul de intrare matrice.in conține pe prima linie numărul natural $N$ . Pe fiecare din următoarele $N$ linii sunt câte $2$ numere întregi separate printr-un spațiu, reprezentând elementele matricii.

Date de ieșire

Fișierul de ieșire matrice.out va conține câte o operație pe linie. O operație este identificată prin tipul ei (poate fi J3, S3, J4 sau S4) și $3$ numere (pentru J3 și S3) sau $4$ numere (pentru J4 și S4) în ordine strict crescătoare, reprezentând rândurile asupra cărora este executată operația. Tipul operației și celelalte numere trebuie să fie separate prin exact un spațiu.
Atenție! Tipul operației este format din două caractere scrise fără spațiu între ele.

Restricții și precizări

$6 \leq N \leq 30 \ 000$ ;
Un subșir strict crescător al unui șir $a_1, a_2, ..., a_N$ este un șir $a_{i_1}, a_{i_2}, ..., a_{i_k}$ , unde $1 ≤ i_1 < i_2 < ... < i_K ≤ N$ și $a_{i_1} < a_{i_2} < ... < a_{i_k}$ ;
Elementele matricii sunt numere întregi mai mari sau egale cu $0$ și mai mici sau egale cu $65 \ 000$ .

Exemplu

matrice.in

matrice.out

S4 1 3 4 5
J3 4 5 6

Explicație

După efectuarea operațiilor, matricea va fi

Lungimea celui mai lung subșir strict crescător de pe prima coloană este $2$ , iar de pe cea de-a doua este $3$ ( $2$ si $3$ sunt mai mici sau egale decât $\lceil \sqrt{N} \rceil = \lceil \sqrt{6} \rceil = 3$ ).

matrice