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

2

Input

5 3

Output

-1

Input

12 5

Output

6 代码实现：

1 #include
         
           2 #include 
          
            3 #include
           
             4 #include
            
              5 #include
             
               6 #include
              
                7 using namespace std; 8 int main() 9 {10 set
               
                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
                
                 v;25 insert_iterator
                 
                  
                    > in_it(v, v.begin());26 copy(a.begin(), a.end(), in_it);27 //printf("%d\n",v.size());28 if(k>v.size())29 printf("-1\n");30 31 else32 {33 printf("%lld\n", v[k-1]);34 }35 36 return 0;37 }