copii

Iliuță și Pandele au învățat la școală operații aritmetice cu numere naturale. Astfel cei doi frați exersează operațiile folosindu-se de o tablă. Iliuță spune un număr natural $X$, iar Pandele scrie pe tablă rezultatul înmulțirii tututor numerelor naturale de la $1$ la $X$. Glumeț, Iliuță șterge cifrele egale cu $0$ de la finalul numărului scris de Pandele.

Ca să îl ierte, Pandele spune și el un număr natural $Y$ și îi cere lui Iliuță să determine un număr natural $Z$ care este cel mai mare divizor al lui $Y$ având un număr impar de divizori.

Cerință

Cunoscându-se numerele spuse de copii, scrieți un program care rezolvă următoarele cerințe:

1. Afișează ultimele $K$ cifre ale produsului calculat de Pandele, după ștergerea cifrelor egale cu $0$ de la finalul acestuia;
2. Afișează numărul $Z$ cu semnificația de mai sus și numărul de divizori ai acestuia.

Date de intrare

Fișierul copii.in conține pe prima linie numărul $C$, care reprezintă numărul cerinței și poate avea doar valorile $1$ sau $2$. Pentru prima cerință fișierul conține pe a doua linie numărul $X$, iar pe cea de a treia linie numărul $K$. Pentru a doua cerință fișierul conține pe a doua linie numărul $Y$.

Date de ieșire

Pentru cerința $1$, pe prima linie a fișierului copii.out se vor afișa cele $K$ cifre cerute, fără spații, în ordine de la stânga la dreapta.
Pentru cerința $2$, pe prima linie se vor afișa, în această ordine, numărul $Z$ determinat și numărul de divizori ai acestuia. Numerele vor fi separate printr-un spațiu.

Restricții și precizări

• $1 \leq X \leq 10^6$;
• $1 \leq Y \leq 10^{12}$;
• $1 \leq K \leq 9$;
• Numărul rămas după ștergerea zerourilor de la finalul produsului are cel puțin $K$ cifre;
• Pentru rezolvarea primei cerințe se acordă $40$ de puncte;
• Pentru rezolvarea celei de a doua cerințe se acordă $60$ de puncte.

Exemplul 1

copii.in

1
12
3

copii.out

016

Explicație

Produsul $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot 11 \cdot 12 = 4790\underline{016}00$.
După ștergerea zerourilor de la finalul produsului, ultimele $3$ cifre sunt $016$.

Exemplul 2

copii.in

2
14641

copii.out

14641 5

Explicație

Cel mai mare divizor al lui $14641$ care are un număr impar de divizori este chiar $14641$.

Exemplul 3

copii.in

1
723432
9

copii.out

813433856

Explicație

După ștergerea zerourilor de la finalul produsului, ultimele $9$ cifre sunt $813433856$.

Exemplul 4

copii.in

2
573194962208

copii.out

286597481104 105

Explicație

Cel mai mare divizor cu un număr impar de divizori este $286597481104$ care are $105$ divizori.