Patron

Ești patron al unui magazin unde se află mai multe produse. Cu o parte din banii strânși ți-ai propus să mergi la ski iarna aceasta. Totuși, după ce s-au pus noile taxe ești în pericol de a nu îți mai permite vacanța mult dorită. Trebuie să acționezi cât mai repede, taxele fiind puse astfel încât să încurce cât mai multă lume. Ele nu sunt date într-o valoare fixă sau în procente cum ar fi normal, ci după următoarea regulă: dacă $p$ este prețul produsului inițial, după aplicarea taxelor, noul preț va fi primul număr prim mai mare sau egal cu $p$. Dacă prețul inițial este deja un număr prim, acesta nu se va modifica. La raftul magazinului tău se află $N$ produse în ordine cu prețuri nu neapărat diferite. Mai întâi ai vrea să afli noile prețuri ale fiecărui produs. Apoi, dacă prețul unui produs s-a mărit cu cel mult un număr natural $L$, atunci produsul este încă profitabil și îl vei păstra. Restul produselor vor fi eliminate după cum urmează. Într-o mutare se pot elimina mai multe produse neprofitabile dacă se află pe poziții consecutive pe raft. Te interesează numărul minim de mutări pentru a rămâne doar cu produse profitabile.

Cerință

• Determinați noile prețuri ale produselor.
• Determinați numărul minim de mutări pentru a rămâne doar cu produse profitabile.

Date de intrare

Pe prima linie a fișierului de intrare patron.in se găsește $C$ reprezentând cerința, apoi $N$ reprezentând numărul de produse de pe raftul magazinului, apoi $L$ reprezentând taxa maximă aplicată unui produs pentru a rămâne profitabil. Pe următoarea linie se află $N$ numere naturale separate prin spațiu reprezentând prețul inițial al fiecărui produs.

Date de ieșire

Dacă $C=1$, pe prima linie a fișierului de ieșire patron.out se vor găsi $N$ numere, reprezentând prețul fiecărui produs după aplicarea taxelor. Dacă $C=2$, pe prima linie se va afla un singur număr natural reprezentând numărul minim de mutări pentru a scoate de pe raft toate produsele neprofitabile.

Restricții și precizări

• Fie $p_i$ prețul inițial al unui produs
• $1 \leq N,L \leq 1 \ 000 \ 000$
• $1 \leq p_i \leq 5 \ 000 \ 000$

Exemplul 1

patron.in

1 10 2
8 14 8 2 3 10 20 4 25 1 

patron.out

11 17 11 2 3 11 23 5 29 2

Explicație

Primul număr prim mai mare sau egal cu $25$ este $29$. Numerele $25$, $26$, $27$, $28$ NU sunt prime.

Exemplul 2

patron.in

2 10 2
8 14 8 2 3 10 20 4 25 1 

patron.out

3

Explicație

Taxele sunt în ordine $3$, $3$, $3$, $0$, $0$, $1$, $3$, $1$, $4$, $1$. Primele 3 produse neprofitabile se află pe poziții consecutive, deci pot fie eliminate printr-o singură mutare.