Fişierul intrare/ieşire:	romania.in, romania.out	Sursă	Algoritmiada 2016 - Runda 2, Seniori
Autor	Andrei Popa, Eugenie Daniel Posdarascu	Adăugată de	Adrian Budau •freak93
Timp execuţie pe test	0.15 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Romania

Fie P un poligon convex regulat cu N vârfuri numerotate în ordine trigonometrică. Ai trasat la un moment dat K diagonale orientate ale acestui poligon, cu proprietatea că oricare două dintre ele nu se intersectează decât, eventual, în capete. În cele ce urmează îl vom numi pe x "sursă" a diagonalei x -> y. Nu ai păstrat desenul întreg, dar ţi-ai notat sursa fiecărei diagonale pe o foaie. Revenind la ea, constaţi că, din motive care nu pot ţine decât de faptul că locuiai cam departe de şcoală, ai scris aceste surse într-o ordine aleatoare. Poţi recupera cele K diagonale?

Date de intrare

Fişierul de intrare romania.in va conţine pe prima sa linie numerele N şi K având semnificaţia din enunţ. A doua linie conţine K numere, reprezentând lista de vârfuri care sunt surse ale diagonalelor.

Date de ieşire

În fişierul de ieşire romania.out se vor afla K linii, fiecare conţinând o pereche x y seminficând faptul că ai ales diagonala orientată dinspre vârful x spre vârful y.

Restricţii

• 3 ≤ N ≤ 100.000
• Pentru teste in valoare de 40 de puncte N ≤ 1.500
• 1 ≤ K ≤ N - 3
• Vârfurile din fişierul de intrare sunt numere naturale din intervalul [1, N].
• Reamintim că se numeşte diagonală a poligonului orice segment care uneşte două vârfuri neconsecutive ale acestuia.
• Se acceptă orice soluţie corectă.
• Dacă vă întrebaţi de ce această problemă se numeşte România: nu mai ştim nici noi.

Exemplu

Cum se trimit solutii?