== include(page="template/taskheader" task_id="chatggg") ==

Poveste şi cerinţă...

Gigel este încântat de evoluţia inteligenţei artificiale şi recent a aflat că cea mai recentă inovaţie în domeniu, un program numit ChatGGG este capabil să sorteze vectori. Fericit că nu mai e necesar să implementeze singur sortările, Gigel decide să se folosească de ChatGGG, dar este dezamăgit că licenţa de evaluare îi permite să sorteze doar subsecvenţe de dimensiuni egale cu jumătate din cea a vectorului dat. Mai mult, el poate să apeleze ChatGGG doar pe 3 subsecvenţe ale unui vector.
 
Scrieţi un program care pentru un vector dat de lungime $N$ îl ajută pe Gigel să selecteze cele 3 subsecvenţe de lungime $N/2$ pe care le va trimite spre ChatGGG pentru sortare.
 
Notă: o subsecvenţă este un vector crescător şi distinct de indici între $1$ şi $N$, în ordine crescătoare, nu neapărat consecutivi.
 
Se acceptă orice soluţie validă.

h2. Date de intrare

Fişierul de intrare $chatggg.in$ ...

Fişierul de intrare $chatggg.in$ conţine pe prima linie numărul de teste $T$. Fiecare test este format din două linii. Pe prima linie se află numărul $N$, ce reprezintă dimensiunea vectorului $A$. Pe a doua linie a fiecărui test se află cele $N$ elemente ale vectorului $A$, separate prin spaţii.

h2. Date de ieşire

În fişierul de ieşire $chatggg.out$ ...

În fişierul de ieşire $chatggg.out$ se vor scrie $3*T$ linii, câte 3 linii pentru fiecare test. Fiecare linie reprezintă o subsecvenţă de dimensiune exact $N/2$, ce va fi sortată. După sortarea celor 3 subsecvenţe, pe rând, vectorul de intrare $A$ trebuie să fie sortat.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $4 ≤ N ≤ 50000$, $N$ este divizibil cu 4
* $1 ≤ T ≤ 30$
 

h2. Exemplu
table(example). |_. chatggg.in |_. chatggg.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|
h3. Explicaţie

...

În primul exemplu începem cu elementele $3, 9, 7, 6$. Sortând subsecvenţa $3, 4$ obţinem $3, 9, 6, 7$. A doua operaţie constă în a sorta subsecvenţa $2, 3$, iar şirul devine $3, 6, 9, 7$. La ultima operaţie sortăm din nou secveţa $3, 4$ obţinând şirul $3, 6, 7, 9$ care este sortat.

== include(page="template/taskfooter" task_id="chatggg") ==