Prinţul Algorel este în încurcătură din nou: a fost prins de Spânul cel Negru în încercarea sa de a o salva pe prinţesă şi acum este închis în Turnul cel Mare. Algorel poate evada dacă găseşte combinaţia magică cu care poate deschide poarta turnului. Prinţul ştie cum se formează această combinaţie magică: trebuie să utilizeze toate cifrele scrise pe uşa turnului pentru a obţine două numere palindroame, astfel încât suma lor să fie minimă, iar această sumă este combinaţia magică ce va deschide uşa. Primul număr palindrom trebuie să aibă cel puţin L cifre, iar cel de-al doilea poate avea orice lungime diferită de 0. Numerele palindroame formate nu pot începe cu cifra 0. Acum interveniţi dumneavoastră în poveste, fiind prietenul său cel mai priceput în algoritmi. Prin noul super-telefon al său, prinţul transmite numărul de apariţii a fiecărei cifre de pe uşa turnului precum şi lungimea minimă L a primului număr, iar dumneavoastră trebuie să-i trimiteţi cât mai repede numerele cu care poate obţine combinaţia magică.
Cerinţă
Având datele necesare, aflaţi două numere palindroame cu care se poate obţine combinaţia magică.
Date de intrare
Prima linie a fişierului de intrare pal.in conţine un număr întreg L reprezentând lungimea minimă a primului număr. Urmează 10 linii: pe linia i+2 se va afla un număr întreg reprezentând numărul de apariţii ale cifrei i, pentru i cu valori de la 0 la 9.
Date de ieşire
Prima linie a fişierului de ieşire pal.out conţine primul număr palidrom, iar cea de-a doua linie conţine cel de-al doilea număr palindrom. Dacă există mai multe soluţii se va scrie doar una dintre ele.
Restricţii
În total vor fi cel mult 100 de cifre 1 ≤ L < 100 şi L va fi mai mic decât numărul total de cifre
Pentru datele de test va exista întotdeauna soluţie: se vor putea forma din cifrele scrise pe uşa turnului două numere care încep cu o cifră diferită de 0, iar primul număr să aibă cel puţin L cifre
Un număr este palindrom dacă el coincide cu răsturnatul său. De exemplu 12321 şi 7007 sunt numere palindroame, în timp ce 109 şi 35672 nu sunt.
Pentru 30% dintre teste, numărul total de cifre va fi cel mult 7; pentru alte 40% din teste numărul total de cifre va fi cel mult 18, iar pentru restul de 30% din teste numărul total de cifre va fi mai mare sau egal cu 30
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie.
Exemple
pal.in
pal.out
Explicaţii
5
3
2
3
0
0
0
0
0
0
0
10223
Pentru acest exemplu avem L = 5, 3 cifre de 0, 2 cifre de 1 şi 3 cifre de 2. Cifrele de la 3 la 9 lipsesc de pe uşa turnului.
Cele două palindroame cu care se generează combinaţia magică sunt 10001 şi 222. Combinaţia magică va fi suma acestora şi anume 10223 (care este suma minimă pe care o putem obţine).