goe

Goe este un copil drăgălaş, dar tare leneş. Nu îi place nici să scrie, nici să numere. Cu greu a fost convins de mama sa să înveţe cifrele, dar de scris tot nu poate să le scrie pe toate. Nu îi plac cifrele $2$, $4$, $5$ şi $7$, iar cifra $6$ o încurcă cu $9$ şi invers. Şi asta nu este tot. Când mama sa îi dă să copieze numere, pentru a exersa scrierea cifrelor, el le scrie în oglindă, adică scrie cifrele în ordinea inversă. De exemplu numărul $138$ va fi scris de Goe $831$.
Mama lui Goe scrie în fiecare zi, în ordine crescătoare, câte $9$ numere naturale, sărind însă peste orice număr divizibil cu $10$, ca în $Figura \ 1$.
Goe copiază zilnic aceste numere. Din păcate, el nu îşi îndreaptă niciuna dintre greşeli: copiază numerele scriindu-le oglindite, nu scrie numerele care conţin cifrele $2$, $4$, $5$ şi $7$ şi înlocuieşte, în continuare cifra $6$ cu $9$ şi invers (vezi $Figura \ 2$).

Cerinţă

Scrieţi un program care să citească numerele naturale nenule $k$, $p$ şi $n$ şi care să determine:

1. Numărul de numere scrise de Goe în primele $k$ zile;
2. Al $p$-lea palindrom scris corect de Goe; un număr este palindrom dacă este egal cu oglinditul său;
3. Cel mai mare număr scris de Goe în primele $n$ zile.

Date de intrare

Fişierul goe.in conţine o singură linie pe care sunt scrise trei numere naturale $k$, $p$ şi $n$, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire goe.out va conţine $3$ linii:

• pe prima linie, se va scrie numărul de numere scrise de Goe în primele $k$ zile;
• pe a doua linie, se va scrie un număr natural reprezentând al $p$-lea palindrom scris corect de Goe;
• pe a treia linie, se va scrie cel mai mare număr scris de Goe în primele $n$ zile.

Restricţii şi precizări

• $1 \leq k \leq 100 \ 000$
• $1 \leq p \leq 750$
• $1 \leq n \leq 32 \ 000 \ 000$
• Pentru rezolvarea cerinţei $1$ se acordă $40\%$ din punctaj, pentru cerinţa $2$, $30\%$ din punctaj şi pentru cerinţa $3$, $30\%$ din punctaj.

Exemplu

goe.in

5 8 3

goe.out

15
111
91

Explicaţie

$15$ numere a scris Goe în primele $5$ zile.
Primele $8$ palindroame scrise corect de Goe sunt: $1$, $3$, $8$, $11$, $33$, $88$, $101$, $111$.
Cel mai mare număr scris de Goe în primele $3$ zile este $91$.