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.

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ța

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 ≤ n < 1 000 000
• 2 ≤ valoarea înscrisă pe un cartonaș ≤ 1 000 000
• Se garantează că pentru fiecare pereche (număr, k), număr 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 ≤ 1000 se acordă 18 puncte
• Pentru rezultate corecte la cerința a doua respectând restricțiile problemei și n ≤ 500 000 se acordă 43 de puncte
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

cufar.in

1 1
30 3

cufar.out

5

Explicație

p = 1, n = 1
Se rezolvă doar prima cerință. Al treilea 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 treilea divizor prim al numărului 30 este 5.
Primul divizor prim al numărului 64 este 2.
Al doilea divizor prim al numărului 105 este 5.
Al treilea divizor prim al numărului 1001 este 13.
Al patrulea divizor prim al numărului 5474 este 23.
Suma căutată va fi S = 5 + 2 + 5 + 13 + 23, de unde rezultă cifrul 48.

#include <bits/stdc++.h>
using namespace std;
ifstream fin("cufar.in");
ofstream fout("cufar.out");

int P[200000] , np;
bool E[1000001];

void ciur(bool E[] , int n)
{
    //ciurul lui Eratostene
    for(int i = 2 ; i <= n ; i++) E[i] = 1;
    for(int i = 2 ; i * i <= n ; i++)
        if(E[i] == 1)
            for(int j = i * i ; j <= n ; j = j + i)
                E[j] = 0;
}

void prime(int n , int P[], int &np)
{
    //numerele prime pana la n
    np = 0;
    for(int i = 2 ; i <= n ; i++)
        if(E[i] == 1) P[++np] = i;
}

int  descnk(int n, int k)
{
    //al k-lea div prim al lui n (fara D)
    int d = 1 , l = 0;
    while(n > 1)
    {
        if(n % P[d] == 0)
        {
            l++;
            if(l == k) return P[d];
            while(n % P[d] == 0) n /= P[d];
        }
        else d++;
        if(n > 1 && P[d] * P[d] > n)
            return n;
    }
    return 0;
}

int main()
{
    ciur(E,1000001);
    prime(1000001,P,np);
    int n , p , x , k;
    fin >> p >> n;
    if(p == 1)
    {
        fin >> x >> k;
        fout << descnk(x,k);
    }
    else
    {
        unsigned long long  s = 0;
        for(int i = 1 ; i <= n ; i++)
           {
               fin >> x >> k;
               s += descnk(x,k);
           }
        fout << s;
        }
    return 0;
}