ŠIOM — Stačiakampio pjaustymas

Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2018_3e2_staciakampis_vyr.in

Rezultatų failas: lmio_2018_3e2_staciakampis_vyr.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Stačiakampio pjaustymas

Irus turėjo stačiakampį, jį perpjovė ir gavo du stačiakampius. Vieną jų atidėjo į šalį, o kitą vėl perpjovė, ir taip kartojo, kol gavo iš viso K stačiakampių. Visi stačiakampių kraštinių ilgiai – sveikieji skaičiai.

Surikiavęs gautus stačiakampius pagal ilgius (t. y. ilgesniąsias kraštines), Irus pastebėjo, kad jos visos yra skirtingos (bet gali būti lygios to paties ar kito stačiakampio trumpesniajai kraštinei).

Užduotis

Irus pamiršo pradinio stačiakampio matmenis. Padėkite jam juos prisiminti.

Pradiniai duomenys

Pirmoje eilutėje pateikiamas stačiakampių skaičius $K$ .

Tolesnėse $K$ eilučių pateikiama po du sveikuosius skaičius $a_i$ ir $b_i$ – stačiakampių ilgiai ir pločiai. Stačiakampiai pateikiami ilgių didėjimo tvarka.

Rezultatai

Pirmoje eilutėje išveskite $P$ – skaičių stačiakampių, kurie galėjo būti pradiniai.

Tolesnėse $P$ eilučių išveskite šių stačiakampių trumpesniųjų kraštinių ilgius didėjimo tvarka.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
3 2 1 3 2 4 2	2 2 4	Pradiniai stačiakampiai galėjo būti supjaustyti tokiais būdais: < insert image here >

Ribojimai

$2\\leqK\\leq100000$