Gigel este un pasionat al triunghiurilor. El colectează beţişoare de diferite lungimi şi le asamblează în diferite triunghiuri. Ieri, el avea 6 beţişoare de lungimi 5, 2, 7, 3, 12 şi 3. Din aceste bețișoare, Gigel a construit un triunghi de laturi 3, 3 şi 5, iar beţişoarele de lungimi 2, 7, 12 au rămas nefolosite pentru că aceste lungimi nu pot forma laturile unui triunghi.
Din acest motiv, Gigel s-a hotărât să facă o colecţie de beţişoare, dintre care oricum ar alege 3 elemente, acestea să nu poată forma laturile unui triunghi, proprietate pe care o vom numi în continuare proprietate anti-triunghi. Gigel, pornind de la setul iniţial de lungimi 2, 7, 12, s-a gândit la două metode de realizare a unei colecţii de 5 beţişoare cu proprietatea anti-triunghi, şi anume:

1.Păstrează cel mai scurt beţişor, cel de lungime 2, şi creează un set nou adăugând alte beţişoare de lungime mai mare sau egală cu cel iniţial. De exemplu, următoarele 5 lungimi sunt corecte: 2, 2, 12, 50, 30.
2.Păstrează toate beţişoarele, şi anume 2, 7,12, pe care le va completa cu alte beţişoare de diferite lungimi (mai scurte sau mai lungi), astfel ca proprietatea anti-triunghi să se păstreze. Următoarele 5 lungimi respectă proprietatea anti-triunghi: 2, 7, 12, 4, 1.

Cerinţă

Cunoscând un şir de n numere naturale nenule a1, a2, …, an având proprietatea anti-triunghi, şi un număr k (k>n), se cere să construiţi un şir de k numere naturale având proprietatea anti-triunghi, în conformitate cu una dintre următoarele două restricţii:

Varianta 1. Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
Varianta 2. Printre cele k elemente ale şirului construit se regăsesc toate elementele şirului iniţial.

Date de intrare

Fişierul de intrare triunghi2.in conţine pe prima linie valorile numerelor v, n şi k, separate prin spaţiu. Linia următoare conţine n numere naturale separate prin spaţiu, ce formează un şir cu proprietatea anti-triunghi.

Date de ieşire

Fişierul de ieşire triunghi2.out va conţine k numere pe o singură linie.

Dacă valoarea lui v este 1, atunci fişierul va conţine k numere naturale cu proprietatea anti-triunghi, separate prin spaţiu, în care cel mai mic element este identic cu minimul şirului dat în fişierul de intrare.

Dacă valoarea lui v este 2, atunci fişierul va conţine k numere naturale cu proprietatea anti-triunghi, separate prin spaţiu, printre care se regăsesc toate elementele şirului iniţial.

Restricţii şi precizări

• 3 ≤ n < k ≤ 46;
• 1 ≤ lungimea unui beţişor ≤ 2.000.000.000;
• Pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte, iar pentru cerinţa a doua se acordă 70 de puncte;
• Se garantează că întotdeauna există soluţie;
• Soluţia nu este unică – se admite orice răspuns corect.

Exemple

triunghi2.in

1 3 5
7 2 12

triunghi2.out

2 2 30 50 12

triunghi2.in

2 3 5
7 2 12

triunghi2.out

1 4 12 7 2

Explicație

Pentru primul exemplu:

v=1, n=3, k=5. În varianta 1 avem de tipărit 5 numere, valoarea minimului este 2 în ambele şiruri.

Pentru al doilea exemplu:

v=2, n=3, k=5. În varianta 2 printre elementele şirului tipărit se regăsesc toate elementele şirului iniţial.