vector、set 练习 k-th divisor

k-th divisor

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.

Example

Input

4 2

Output

Input

5 3

Output

-1

Input

12 5

Output

6
代码实现：

 1 #include<cstdio>
 2 #include <set>
 3 #include<vector>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 int main()
 9 {
10     set<long long int>a;
11     long long int n,k;
12     long long int p1,pp;
13     scanf("%lld%lld",&n,&k);
14     pp=sqrt(n);
15     for(int i=1; i<=pp; i++)
16     {
17         p1=n%i;
18         if(p1==0)
19         {
20             a.insert(n/i);
21             a.insert(i);
22         }
23     }
24     vector<long long int>v;
25     insert_iterator<vector<long long int> > in_it(v, v.begin());
26     copy(a.begin(), a.end(), in_it);
27     //printf("%d
",v.size());
28     if(k>v.size())
29         printf("-1
");
30 
31     else
32     {
33         printf("%lld
", v[k-1]);
34     }
35 
36     return 0;
37 }