secv

Se consideră un şir $S$, iniţial vid. Asupra acestuia se efectuează patru operaţii:

1. insert($k, e$): inserează în $S$ elementul e pe poziţia $k$;
2. access($k$): întoarce elementul de pe poziţia $k$;
3. reverse($i, j$) : schimbă ordinea elementelor din secvenţa $S[i \ \dots \ j]$;
4. delete($i, j$) : Şterge subsecvenţa $S[i \ \dots \ j]$.

Cerință

Se cere să se răspundă la toate operaţiile de tipul $2$ şi să se afişeze elementele secvenţei $S$ după efectuarea tuturor operaţiilor.

Date de intrare

Pe prima linie a fişierului de intrare secv.in se vor găsi două numere naturale, primul reprezentând numărul operaţiilor din fişier, iar al doilea va fi $1$ dacă există operaţia reverse şi $0$ dacă nu există. Următoarele linii vor fi de patru tipuri, corespunzătoare fiecărei operaţii:

1. $I \ k \ e$: insert($k, e$), unde $e$ este un număr natural cuprins în intervalul $[0, 10^9]$ iar $k$ un număr natural cuprins în intervalul $[1, n+1]$.
2. $A \ k$: acces($k$), unde $1 \leq k \leq n$.
3. $R \ i \ j$: reverse($i, j$), unde $1 \leq i \leq j \leq n$.
4. $D \ i \ j$: delete($i, j$), unde $1 \leq i \leq j \leq n$.
   Cu $n$ am notat lungimea secvenţei.

Date de ieșire

În fişierul de ieşire secv.out se vor tipări pe câte un rând răspunsurile operaţiilor de tipul $2$ în ordinea în care apar în fişierul de intrare. Pe ultima linie se va tipări secvenţa $S$ după efectuarea tuturor operaţiilor.

Restricții și precizări

• Numărul operaţiilor insert nu va depăşi $250 \ 000$.
• Numărul total al operaţiilor nu va depăşi $750 \ 000$.
• Operaţia insert($k, e$) va transforma secvenţa $S$: $s_1 \ s_2 \dots s_k \dots s_n$ în S’: $s_1 \ s_2 \dots e \ s_k \dots s_n$.
• Operaţia reverse($i, j$) va transforma secvenţa $S$: $s_1 \dots s_{i-1} \ s_i \ s_{i+1} \dots s_{j-1} \ s_j \ s_{j+1} \dots s_n$ în S’: $s_1 \dots s_{i-1} \ s_j \ s_{j+1} \dots s_{i+1} \ s_i \ s_{j+1} \dots s_n$.
• Operaţia delete($i, j$) va transforma secvenţa $S$: $s_1 \dots s_{i-1} \ s_i \ s_{i+1} \dots s_{j-1} \ s_j \ s_{j+1} \dots s_n$ în S’: $s_1 \dots s_{i-1} \ s_{j+1} \dots s_n$.
• Se garantează că operaţiile $2$, $3$ şi $4$ nu se vor efectua asupra unei secvenţe vide.
• Pentru $15\%$ din teste numărul operaţiilor insert nu va depăşi $35 \ 000$ iar numărul total al operaţiilor $100 \ 000$. Pentru aceste teste va exista operaţia reverse.
• Pentru încă $25\%$ din teste operaţia reverse nu se va regăsi.

Exemplu

secv.in

13 1
I 1 1
I 2 2
I 3 3
R 2 3
I 4 4
I 3 5
A 4
R 1 3
D 2 3
A 3
I 2 1
R 1 3
D 3 3

secv.out

2
4
2 1 4

Explicație

Secvenţa S devine succesiv: $(1), (1 \ 2), (1 \ 2 \ 3), (1 \ 3 \ 2), (1 \ 3 \ 2 \ 4), (1 \ 3 \ 5 \ \underline{2} \ 4), (5 \ 3 \ 1 \ 2 \ 4), (5 \ 2 \ \underline{4}), (5 \ 1 \ 2 \ 4), (2 \ 1 \ 5 \ 4), (2 \ 1 \ 4)$. Numerele subliniate sunt răspunsurile la operaţiile de tipul $2$.