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 n şi care să determine numărul de numere scrise de Goe în primele k zile, al p-lea palindrom scris corect de Goe; un număr este palindrom dacă este egal cu oglinditul său şi 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 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
• 1≤ k ≤ 100000
• 1≤ p ≤ 750
• 1≤ n ≤ 32000000
Exemple
goe.in
goe.out
Explicaţii
5 8 3
15
111
91
15 numere a scris Goe în primele 5 zile.
Primele 8 palindromuri 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.
