Fişierul intrare/ieşire:	zalmoxis.in, zalmoxis.out	Sursă	BOI 2018
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Zalmoxis

Tanaka a devenit interesat de Mitologia Dacă (dacii au trăit în zona României înaintea romanilor). În această mitologie, Zalmoxis era zeul suprem, iar Pleistoros zeul războiului. În noua interpretare a mitologiei făcută de Tanaka, Zalmoxis are o nouă putere, ZalLovitura, şi îi plac ZalSecvenţele.

ZalLovitura este un atac care poate fi aplicat pe secvenţe non-negative de întregi. Atacul constă în alegerea unui întreg strict pozitiv x din secvenţă şi înlocuirea lui cu alte două valori x-1. De exemplu:

• {1} {0, 0}
• {1, 23, 3} {1, 22, 22, 3}
• Dar nu este cazul ca {1, 3} {2, 1, 2}, deoarece ordinea din secvenţă contează.

ZalSecvenţele – secvenţele care îi plac lui Zalmoxis – sunt următoarele:

• Secvenţa {30}.
• O secvenţă care poate fi obţinută prin aplicarea unei ZalLovituri altei ZalSecvenţe.

De exemplu, , {29, 29} şi {29, 28, 27, 27} sunt ZalSecvenţe, dar {28, 29, 28} nu este.
Pentru început, Zalmoxis crează o ZalSecvenţă de lungime N + K. După aceasta, unul dintre inamicii săi distruge K dintre valorile din această secvenţă, lăsând doar N valori. Fie notată această secvenţă cu S. Cu N, K si S date, introduceţi K valori în S astfel încăt să creaţi orice ZalSecvenţă de lungime N + K. Se garantează ca pentru orice test există solutie.

Date de intrare

Prima linie a fisierului de intrare zalmoxis.in conţine numerele întregi pozitive N si K.
A doua linie conţine N întregi ne-negativi, valorile lui S.

Date de ieşire

Prima linie a fisierului de iesire zalmoxis.out conţine numerele întregi nenegative ale ZalSecventei de lungime N + K

Restricţii

• 1 ≤ N ≤ 1.000.000
• 1 ≤ K ≤ 1.000.000
• 1 ≤ N + K ≤ 1.000.000
• Secvenţa din fişierul de intrare este un subşir al unei ZalSecvenţe de lungime N + K.
• Pentru teste in valoare de 30 de puncte, K = 1.
• Toate testele folosite nu sunt grupate.

Exemplu

Explicaţie

În primul exemplu, {29, 27, 25, 25, 26, 28} poate fi obţinută din {30} prin următoarele ZalLovituri:

{30} → {29, 29} → {29, 28, 28} → {29, 27, 27, 28} → {29, 27, 26, 26, 28} → {29, 27, 25, 25, 26, 28}

În al doilea exemplu, {29, 28, 27, 26, 25, 25} poate fi obţinută din {30} prin următoarele ZalLovituri:

{30} → {29, 29} → {29, 28, 28} → {29, 28, 27, 27} → {29, 28, 27, 26, 26} → {29, 28, 27, 26, 25, 25}

Cum se trimit solutii?