Succesori

Rareș a învățat la ora de informatică despre conceptul de succesor. Succesorul unui număr natural nenul $X$ este numărul $S(X)$ obținut din $X$, astfel: fiecare cifră strict mai mică decât $9$ se înlocuiește cu cifra mai mare cu o unitate, iar cifra $9$ se înlocuiește cu cifra $0$. Din numărul obținut, se elimină cifrele nule aflate pe primele poziții, iar numărul $0$ nu are succesor. De exemplu:

• $S(12) = 23$;
• $S(944)=55$;
• $S(795)=806$;
• $S(999)=0$;
• $S(999912)=23$;
• $S(9)=0$.

Mihai, colegul lui Rareș, îi propune acestuia următoarea problemă: se dau două numere naturale $n$, $p$ și un șir de $n$ numere naturale $x_1, x_2, \dots, x_n$. Se scriu cele $n$ numere dispuse unul sub celălalt, câte unul pe un rând. Pe fiecare rând, se adaugă numere, după următoarea regulă:

• Dacă ultimul număr de pe un rând este nenul, atunci, la rândul respectiv, se adaugă succesorul acelui ultim număr.
• După ce s-au completat toate rândurile, și astfel fiecare rând se termină cu valoarea 0, se iau toate numerele de pe cele $n$ rânduri și se formează un șir.
• Se ordonează crescător șirul obținut.

De exemplu, dacă $n=3$, iar cele 3 numere date inițial de Mihai sunt $78, 9552$ și $752$, avem inițial 3 rânduri, fiecare cu câte un număr:

1. $78$
2. $9552$
3. $752$

După ce se completează rândurile cu succesori, cele 3 rânduri complete vor fi:

1. $78$ $89$ $90$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$ $0$
2. $9552$ $663$ $774$ $885$ $996$ $7$ $8$ $9$ $0$
3. $752$ $863$ $974$ $85$ $96$ $7$ $8$ $9$ $0$

Cu toate numerele, se formează șirul crescător următor:

Cerință

Cunoscând numerele naturale $n$, $p$ și cele $n$ numere naturale inițiale, determinați numărul situat pe poziția $p$ în șirul final obținut, dacă pozițiile sunt numerotate începând cu $1$.

Date de intrare

Pe prima linie a fișierului succesori.in se află două numere naturale $n$ și $p$, separate prin spațiu, cu semnificația din enunț. Pe următoarele $n$ linii ale fișierului, se află cele $n$ numere naturale nenule $x_1, x_2, \dots, x_n$, câte unul pe linie, cu semnificația din enunț.

Date de ieșire

Pe singura linie a fișierului succesori.out se va afla un singur număr natural, reprezentând numărul situat pe poziția $p$ în șirul sortat, format după regula din enunț.

Restricții și precizări

• $1 \leq n \leq 10^6$;
• $1 \leq x_n < 10^{18}$;
• $p <$ numărul total de numere din șirul ordonat obținut.

Exemplul 1

succesori.in

3 23
78
9552
752

succesori.out

96

Explicație

Exemplul este explicat in enunțul problemei.

Exemplul 2

succesori.in

5 65
23314
12
10019324124
5566778
1423

succesori.out

89

Explicație

Se scriu pe rând succesorii pe fiecare rând, conform regulei. În șirul sortat obținut, pe poziția $65$, se află numărul $89$.

Exemplul 3

succesori.in

10 15
145123187
292253412
545220314
645144712
945114524
245100187
525656715
443123187
577856712
845223886

succesori.out

2

Explicație

În șirul sortat obținut după scrierea succesorilor, pe poziția $15$, se află numărul $2$.

Exemplul 4

succesori.in

10 301
145123187698456712
122133567292253412
545220314744452740
645123187698456712
945123187222400714
245100187698456712
245123180025656715
443123187698456716
545223112577856712
745223886198456718

succesori.out

34596

Explicație

În șirul sortat obținut după scrierea succesorilor, pe poziția $301$, se află numărul $34596$.