Triunghi

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ăstreză 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 $a_1, a_2, ..., a_n$ 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

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

Date de intrare

Fişierul de intrare triunghi.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 propietatea anti-triunghi.

Date de ieșire

Fişierul de ieşire triunghi.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 \leq n < k \leq 46$
• $1 \leq$ lungimea unui beţişor $\leq 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.

Exemplul 1

triunghi.in

1 3 5
7 2 12

triunghi.out

2 2 30 50 12

Explicație

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

Exemplul 2

triunghi.in

2 3 5
7 2 12

triunghi.out

1 4 12 7 2

Explicație

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