Rezolvare PBinfo #4767

Trei nave spațiale, fiecare transportând n extratereștri din trei galaxii diferite (Galaxia Algorithma, Nebulosa Recursiv și Calea Protocol), au ajuns la Olimpiada de Informatică din galaxia Calea Informateea. Pentru a celebra această ocazie, toți extratereștrii își doresc să facă o fotografie de grup împreună. Înălțimile extratereștrilor sunt foarte variate, de la nanometri la kilometri. Din acest motiv, pentru a se asigura că se văd toți în fotografie, extratereștrii trebuie să se așeze pe trei rânduri:

• Primul rând: Extratereștrii cei mai mici de statură (în ordine descrescătoare a înălțimilor de la stânga la dreapta).
• Al doilea rând: Extratereștrii cu înălțimi intermediare ordonați descrescător de la stânga la dreapta
• Al treilea rând: Extratereștrii cei mai înalți ordonați descrescător de la stânga la dreapta.

Cerința

Fiind dat numărul natural C reprezentând numărul cerinței, un număr natural n reprezentând numărul de extratereștri din fiecare navă și apoi trei șiruri de n numere naturale nenule cu maximum 9 cifre fiecare, scrieți un program care rezolvă următoarele cerințe:
1) Dacă C = 1, atunci determină înălțimea maximă și minimă a extratereștrilor din toate cele 3 nave.
2) Dacă C = 2, atunci determină ordinea extratereștrilor în poză, pe fiecare dintre cele trei rânduri, de la stânga la dreapta, ordonați descrescător după înălțime.

Date de intrare

Fișierul de intrare poza.in conţine pe prima linie numărul C reprezentând cerința (1 sau 2) și numărul natural n, iar pe următoarele trei linii câte un șir de n numere, valorile de pe aceeași linie fiind separate prin câte un spațiu.

Date de ieșire

Dacă cerința C = 1, atunci pe prima linie a fişierului de ieşire poza.out se vor scrie două numere naturale separate printr-un spațiu reprezentând înălțimea maximă și cea minimă a tuturor extraterestrilor din cele trei nave.
Dacă cerința C = 2, atunci fişierul de ieşire poza.out va conține trei șiruri cu n valori numere naturale, reprezentând înălțimile extratereștrilor, începând cu cei mai scunzi, fiecare șir fiind scris pe câte un rând. Pe fiecare rând, extratereștrii vor fi așezați de la stânga la dreapta, în ordinea descrescătoare a înălțimilor, valorile de pe fiecare rând fiind separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100.000, 1 ≤ c ≤ 2
• 1 ≤ a[i] ≤ 1.000.000.000 (Se asigură că nu vor fi mai mult de n extratereștri cu aceeași înălțime)
• Pentru 20 de puncte cerinţa este 1.
• Pentru 20 de puncte cerinţa este 2 și n ≤ 1000
• Pentru alte 50 de puncte cerința va fi 2, iar n > 1000
• 10 puncte se acordă pentru testele din enunț.

Exemplul 1:

poza.in

1 4
13 20 24 3
12 100 100 2
17 18 98 23

poza.out

100 2

Explicație

Înălțimea maximă este 100 și înălțimea minima este 2.

Exemplul 2:

poza.in

2 4
24 20 13 3
100 100 12 2
98 23 18 17

poza.out

13 12 3 2
23 20 18 17
100 100 98 24

Explicație

Pe prima linie sunt extratereștrii cei mai scunzi, ordonați descrescător de la stânga la dreapta. Pe următoarea linie sunt extratereștrii de înălțime medie ordonați descrescător de la stanga la dreapta iar pe ultima linie sunt cei mai înalți extratereștri.