triaj

Într-o zonă unde se face triajul vagoanelor sunt exact $1013$ linii ferate paralele, numerotate de la $1$ la $1013$, legate între ele prin două linii laterale plus o linie suplimentară ca în figură.

Pe linia $1$ se află iniţial $N$ vagoane, fiecare vagon având un număr scris pe el. Numerele de pe vagoane nu sunt neapărat distincte. Ronnie „The Rocket” O’Sullivan, care s-a lăsat de snooker şi s-a angajat la CFR ca să o impresioneze pe sora lui Alex, doreşte să ordoneze crescător vagoanele tot pe linia $1$, putând face doar următorul tip de operaţie: selectează o linie şi un capăt (stânga sau dreapta) din care extrage o secvenţă de oricâte vagoane şi plasează fiecare vagon pe orice linie în orice capăt. El poate efectua cel mult două operaţii de extragere din fiecare linie, câte maximum una pentru fiecare capăt. Dar poate efectua oricâte operaţii de plasare a vagoanelor pe orice linie. Linia suplimentară şi cele laterale sunt doar pentru a asigura transportul vagoanelor dintr-o parte în alta, pe acestea neputând staţiona vagoane.

Cerință

Să se determine o succesiune de operaţii de extragere şi plasare a vagoanelor pe care le poate efectua Ronnie astfel încât în final pe linia $1$ vagoanele să fie ordonate crescător după numerele asociate.

Date de intrare

Fişierul de intrare triaj.in conţine numărul natural $N$. Pe linia a doua se află $N$ numere naturale separate prin câte un spaţiu reprezentând, de la stânga la dreapta, valorile asociate celor $N$ vagoane aflate pe linia 1.

Date de ieșire

Fişierul de ieşire triaj.out va conţine pe prima linie un număr natural $M$ reprezentând numărul de operaţii efectuate. Pe următoarele $M$ linii se vor afla descrise fiecare din cele $M$ operaţii. Fiecare linie mai întâi conţine trei numere naturale $L$, $C$ şi $V$, unde $L$ este numărul liniei de unde se extrag vagoane, $C$ este capătul de unde se extrag ($0$ – capătul stâng, $1$ – capătul drept), $V$ numărul de vagoane extrase. Urmează pe aceeaşi linie $2 \cdot V$ numere naturale, câte două pentru fiecare vagon reprezentând linia şi capătul unde va fi introdus.

Restricții și precizări

• $3 \leq N \leq 1 \ 000 \ 000$
• Numerele de pe vagoane sunt valori naturale cel mult egale cu $2^{30}$
• Pentru fiecare test, dacă ordonarea vagoanelor se face corect, va fi acordat punctajul în funcţie de $x$, acesta fiind numărul maxim de extrageri de la un capăt al unei linii:
• Dacă $x \leq 1$, se primeşte întregul punctaj
• Dacă $x \leq 2$, se primeşte $80\%$ din punctaj
• Dacă $x \leq 4$, se primeşte $60\%$ din punctaj
• Dacă $x \leq 8$, se primeşte $40\%$ din punctaj
• Dacă $x > 8$, se primeşte $20\%$ din punctaj
• Pentru $15\%$ din teste, valorile de pe vagoane sunt de cel mult $2 \ 000$
• Pentru încă $20\%$ din teste, $N \leq 2 \ 000$
• Pentru încă $40\%$ din teste, valorile de pe vagoane sunt de cel mult $1 \ 000 \ 000$
• Ancorat în sinergia progresului CFR, infatigabilul Ronnie a evitat cu sagacitate meandrele inextricabile ale crizei economice, având un salariu mirobolant.

Exemplu

triaj.in

4
2 6 13 2

triaj.out

4
1 1 4 2 1 13 1 6 1 2 1
13 0 1 1 0
6 0 1 1 0
2 0 2 1 0 1 0

Explicație

Prima operaţie: se extrag de la linia $1$, capătul drept, $4$ vagoane, deci în ordinea $2, 13, 6, 2$. Vagonul cu valoarea $2$ se pune la linia $2$, capătul drept; cel cu valoare $13$ se pune la linia $13$, capătul drept; al treilea vagon (de valoare $6$) se pune la capătul drept al liniei $6$; ultimul vagon se pune la capătul drept al liniei $2$.

A doua operaţie: se extrage de la linia $13$, de la capătul stâng, un vagon, care se pune pe la capătul stâng al liniei $1$.

A treia operaţie: se extrage de la linia $6$, din capătul stâng al liniei, un vagon, care se pune capătul stâng al liniei $1$.

A patra operaţie: Se extrag de la linia $2$ cele două vagoane de valoare $2$ şi se depun ambele pe la capătul stâng la linia $1$.