Codeforces Problem 762A (K-th-divisor)

Codeforces Problem 762A 

(K-th-divisor)

Problem link : 
http://codeforces.com/problemset/problem/762/A

You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn't exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.

Input

The first line contains two integers n and k (1 ≤ n ≤ 10¹⁵, 1 ≤ k ≤ 10⁹).

Output

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.

Examples

input

4 2

output

2

input

5 3

output

-1

input

12 5

output

6

Note

In the first example, number 4 has three divisors: 1, 2 and 4. The second one is 2.

In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is -1.

Solution : 

#include<bits/stdc++.h>
using namespace std;
vector<long long int>ara;
int main()
{
  long long int n,i,k,g=0,sq,d;
    cin>>n>>k;
    sq=sqrt(n);
    for(i=1; i<=sq; i++)
    {
        if(n%i==0)
        {
            d=n/i;
            if((d*d)!=n)
            {
                ara.push_back(d);
                g++;

            }
            ara.push_back(i);
            g++;
        }
    }
    sort(ara.begin(),ara.end());
    if(k>g) printf("-1\n");
    else printf("%lld\n",ara[k-1]);

    return 0;
}
//LanguageC++