produs

Se da un sir de N cifre. Se vor insera K semne * (inmultit) in acest sir.
Se obtine astfel un produs ai carui factori sunt numerele formate din cifrele dintre doua semne *, sau dintre un semn * si unul din capetele sirului. Factorii respectivi vor avea cel putin o cifra, cel mult C cifre si nu pot incepe cu cifra 0.

Cerinta

Determinati pozitiile in care se vor insera semnele *, astfel incat produsul obtinut sa fie maxim.

Date de intrare

Fisierul de intrare produs.in contine pe prima linie numerele naturale N, K si C.
Pe a doua linie a fisierului se afla cele N cifre din sir, separate prin cate un spatiu.

Date de iesire

Fisierul produs.out va contine o linie pe care se va scrie sirul rezultat dupa inserarea celor K semne * in sirul de cifre. Elementele sirului (cifre si semne *) nu vor fi separate prin spatii.

Restrictii si precizari

- 1<=N<=500;
-0<=K<N si K<=200;
-1<=C<=9;
- toate testele date vor admite solutie. De exemplu, un test cu N=100, K=20 si C=2 nu admite solutie; astfel de cazuri nu vor fi date la evaluare.
- in cazul in care exista mai multe solutii, afisati una oarecare.

Exemplu
produs.in produs.out
4 1 3
2 3 4 5 		234*5
Timp maxim de executie/test: 0.1 secunde

Mihai Stroe
Bucuresti
Contact: mihai_stroe at yahoo.com