Cioc

Cioc, un elev abia aterizat în clasa a IX-a, primește de la doamna profesor de informatică un șir de n numere naturale pe care trebuie să îl prelucreze. Astfel, băiatul trebuie să scrie după fiecare dintre cele k cele mai mici elemente dublul lor. Dacă cel mai mare dintre aceste numere se repetă și deja se depășesc cele k elemente prevăzute, doamna profesor îi dă libertatea băiatului de a modifica valoarea lui k astfel încât să cuprindă și aceste valori. De exemplu, dacă n = 7, v[] = {1, 4, 6, 2, 3, 4, 5} și k = 4, atunci, în urma prelucrării, șirul v devine {1, 2, 4, 8, 6, 2, 4, 3, 6, 4, 8, 5}, și deci \( k_{final}=5 \).

Cerința

Cunoscându-se n, șirul v și k, să se afișeze:

• 1. Numărul \( k_{final} \);
• 2. Vectorul după prelucrare.

Date de intrare

Fișierul de intrare cioc.in conține pe prima linie numerele c (mereu 1 sau 2, reprezentând cerința ce trebuie rezolvată), n, k, iar următoarea linie va conține n numere întregi, reprezentând elementele vectorului inițial.

Date de ieșire

Fișierul de ieșire cioc.out va conține pe prima linie:

• Dacă c = 1, atunci numărul \( k_{final} \);
• Dacă c = 2, atunci vectorul după prelucrare.

Restricții și precizări

• 1 ≤ n, k ≤ 100.000;
• \( 1 \leq v[i] \leq 2^{60} \);
• Pentru 40% din teste, c=1.

Exemplu:

cioc.in

1 7 4
1 4 6 2 3 4 5

cioc.out

5

Explicație

k-ul inițial nu este suficient de cuprinzător (numărul 4 se repetă).

cioc.in

2 7 4
1 4 6 2 3 4 5

cioc.out

1 2 4 8 6 2 4 3 6 4 8 5

Explicație

Acesta este exemplul din enunț.