cufar

Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt $n$ cartonașe. Pe fiecare cartonaș este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonașe sunt distincte între ele.

Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaș din cutie și apoi determină valoarea magică asociată numărului natural scris pe cartonaș. Pentru fiecare cartonaș valoarea magică este dată de al $k$-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obținute pentru cele $n$ cartonașe și apoi să introducă în ordine cifrele valorii obținute, pentru a descuia lada.

Cerințe

Deoarece vrăjitoarea nu are timp la dispoziție vă roagă pe voi să o ajutați să rezolve următoarele probleme:

1. Să afle valoarea magică pentru un cartonaș dat;
2. Să afle cifrul cufărului.

Date de intrare

Fișierul de intrare este cufar.in.
Pe prima linie a fișierului de intrare se găsesc o valoare $p$ care poate fi doar $1$ sau $2$ și numărul $n$ de cartonașe despărțite prin câte un spațiu.

Dacă $p$ este $1$ pe linia a doua a fișierului de intrare se găsesc două valori reprezentând numărul de pe cartonașul dat și valoarea $k$, separate printr-un spațiu, cu semnificația de mai sus.

Dacă $p$ este $2$ pe următoarele $n$ linii ale fișierului de intrare se găsesc câte două valori, separate prin câte un spațiu, reprezentând numărul de pe cartonaș și valoarea lui $k$ pentru fiecare din cele $n$ cartonașe.

Date de ieşire

Fișierul de ieșire este cufar.out.
Dacă valoarea lui $p$ este $1$, atunci se va rezolva doar cerința 1 și fișierul de ieșire va conține pe prima linie valoarea magică asociată cartonașului dat.
Dacă valoarea lui $p$ este $2$, atunci se va rezolva doar cerința 2 și fișierul de ieșire va conține pe prima linie cifrul necesar deschiderii cufărului.

Restricţii și precizări

• $1 \leq n < 1\ 000\ 000$
• Valoarea înscrisă pe un cartonaș este un număr între $2$ și $1\ 000\ 000$.
• Se garantează că pentru fiecare pereche $(nr, k)$ din fișierul de intrare, $nr$ are cel puțin $k$ divizori primi.
• Pentru rezolvarea corectă a cerinței 1 se acordă 18 puncte.
• Pentru rezolvarea corectă a cerinței 2 se acordă 72 de puncte.
• Pentru rezultate corecte la cerința a doua respectând restricțiile problemei și $n \leq 1\ 000$ se acordă 18 puncte.
• Pentru rezultate corecte la cerința a doua respectând restricțiile problemei și $n \leq 500\ 000$ se acordă 43 de puncte.
• Din oficiu se acordă 10 puncte.

Exemplul 1

cufar.in

1 1
30 3

cufar.out

5

Explicație

$p = 1$, $n = 1$. Se rezolvă doar prima cerință.
Al $3$-lea divizor prim al numărului $30$ este $5$.

Exemplul 2

cufar.in

2 5
30 3
64 1
105 2
1001 3
5474 4

cufar.out

48

Explicație

$p = 2$, $n = 5$. Se rezolvă doar a doua cerință.
Al $3$-lea divizor prim al numărului $30$ este $5$.
Primul divizor prim al numărului $64$ este $2$.
Al $2$-lea divizor prim al numărului $105$ este $5$.
Al $3$-lea divizor prim al numărului $1001$ este $13$.
Al $4$-lea divizor prim al numărului $5474$ este $23$.
Suma căutată va fi $S = 5 + 2 + 5 + 13 + 23$, de unde rezultă cifrul $48$.