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:
* 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$.
* 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$.
* 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$ .
* 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$.
h2. Cerinta
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:
* Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
* Printre cele $k$ elemente ale şirului construit se regăsesc toate elementele şirului iniţial.
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:
* Cel mai mic element este identic cu cel mai mic element din şirul iniţial.
* Printre cele $k$ elemente ale şirului construit se regăsesc toate elementele şirului iniţial.
h2. Date de intrare
* $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
* 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.
