Problem: 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 ≤ 1015, 1 ≤ k ≤ 109).

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 (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
  public class Tester {
	//static long sum=0,sum1=Long.MAX_VALUE;
	//DecimalFormat df = new DecimalFormat("#.#####");
		static int visited[] = new int[100005];
	public static final long MOD = (long) (1e9 + 7);
		static long h[];
		static long j;
			// Driver program to test above function
		    public static void main(String args[])
		     {
		    	Scanner sc=new Scanner(System.in);
		    	InputReader in = new InputReader(System.in);
		  	  	OutputStream outputStream = System.out;
		  	  	PrintWriter out = new PrintWriter(outputStream);
		  	  	long n=in.nextLong();
		  	  	long k=in.nextLong();
		  	  	long count=0,flag=0;
		  	  	long i=0;
//		  	  	PriorityQueue q=new PriorityQueue();
		  	  	ArrayList<Long> arr=new ArrayList();
		  	  	
		  	  	int count1=0;
		  	  	for( i=1;i<=Math.sqrt(n);i++)
		  	  	{
		  	  		if(n%i==0)
		  	  		{
		  	  			//out.println("AAYA "+i);
		  	  			if((n/i)!=i)
		  	  			{
		  	  				count+=2;
		  	  				arr.add(i);
		  	  				arr.add(n/i);
		  	  			}
		  	  			else
		  	  			{
		  	  				count++;
		  	  				arr.add(i);
		  	  				count1++;
		  	  			}
		  	  		}
		  	  		
		  	  	}
		  	  	Collections.sort(arr);
		  	  	
		  	  	if(arr.size()>=k)
		  	  		out.println(arr.get((int)(k-1)));
		  	  	else
		  	  		out.println(-1);
		  	  	out.close();	
		  	  }
		    static int sum(int a,int b)
		    {
		    	int sum=0;
		    	if(a>b)
		    		return 0;
		    	else
		    	{
		    		for(int i=a;i<=b;i++)
		    		{
		    			sum+=i;
		    		}
		    		return sum;
		    	}
		    }
		    static int BinarySearch(String s,String[] arr)
		    {
		    	int l=0;
		    	int r=arr.length-1;
		    	while(l<=r)
		    	{
		    		int mid=(l+r)/2;
		    		if(arr[mid].compareTo(s)==0)
		    		{
		    			return 1;
		    		}
		    		else if(arr[mid].compareTo(s)>0)
		    		{
		    			l=mid+1;
		    		}
		    		else
		    		{
		    			r=mid-1;
		    		}
		    	}
		    	return -1;
		    }
		    static int BFS(ArrayList<ArrayList<Integer>> adj, int root)
		    {
		    	    Queue<Integer> q=new LinkedList<Integer>();
		    	    visited[1]=1;
				 	visited[root]=1;
				 	//dis[root]=0;
				    q.add(root);
				    int count=1;
				 	while(!q.isEmpty())
				 	{
				 		int element=q.remove();
				 		System.out.println("element is "+element);
				 		for (int i : adj.get(element)) {
							if (visited[i] == 0) {
				 			{	
					 			System.out.println("i is "+i);
				 				visited[i]=1;
				 				q.add(i);
				 				//dis[i]=dis[element]+6;
				 				count++;
				 			}
				 				
				 			}
				 	    }
				 	}
				 	return count;
		    }
		    static int ceilSearch(ArrayList<Pair> arr, int low, int high, long x)
		    {
		      int mid;    
		     
		      /* If x is smaller thint n=in.nan or equal to the first element,
		        then return the first element */
		      if(x <= arr.get(low).getIndex())
		        return low; 
		     
		      /* If x is greater than the last element, then return -1 */
		      if(x > arr.get(high).getIndex())
		        return -1;  
		     
		      /* get the index of middle element of arr[low..high]*/
		      mid = (low + high)/2;  /* low + (high - low)/2 */
		     
		      /* If x is same as middle element, then return mid */
		      if(arr.get(mid).getIndex() == x)
		        return mid;
		         
		      /* If x is greater than arr[mid], then either arr[mid + 1]
		        is ceiling of x or ceiling lies in arr[mid+1...high] */ 
		      else if(arr.get(mid).getIndex() < x)
		      {
		        if(mid + 1 <= high && x <= arr.get(mid+1).getIndex())
		          return mid + 1;
		        else
		          return ceilSearch(arr, mid+1, high, x);
		      }
		     
		      /* If x is smaller than arr[mid], then either arr[mid] 
		         is ceiling of x or ceiling lies in arr[mid-1...high] */   
		      else
		      {
		        if(mid - 1 >= low && x > arr.get(mid-1).getIndex())
		          return mid;
		        else    
		          return ceilSearch(arr, low, mid - 1, x);
		      }
		    }
		    static int floorSearch(long arr[], int low, int high, long x)
		    {
		      int mid;    
		     
		      /* If x is smaller than or equal to the first element,
		        then return the first element */
		      if(x >= arr[high])
		        return high; 
		     
		      /* If x is greater than the last element, then return -1 */
		      if(x < arr[low])
		        return -1;  
		     
		      /* get the index of middle element of arr[low..high]*/
		      mid = (low + high)/2;  /* low + (high - low)/2 */
		     
		      /* If x is same as middle element, then return mid */
		      if(arr[mid] == x)
		        return mid;
		         
		      /* If x is greater than arr[mid], then either arr[mid + 1]
		        is ceiling of x or ceiling lies in arr[mid+1...high] */ 
		      else if(arr[mid] < x)
		      {
		        if(mid + 1 <= high && x < arr[mid+1])
		          return mid;
		        else
		          return floorSearch(arr, mid+1, high, x);
		      }
		     
		      /* If x is smaller than arr[mid], then either arr[mid] 
		         is ceiling of x or ceiling lies in arr[mid-1...high] */   
		      else
		      {
		        if(mid - 1 >= low && x >= arr[mid-1])
		          return mid-1;
		        else    
		          return floorSearch(arr, low, mid - 1, x);
		      }
		    }
		    static long binaryExponentiation(long x,long n)
		    {
		        long result=1;
		        while(n>0)
		        {
		            result=(result%MOD*x%MOD)%MOD;
		            n--;
		        }
		        return result;
		    }
		    static long nCr(int n, int r){
				long rfact=1, nfact=1, nrfact=1,temp1 = n-r ,temp2 = r;
				if(r>n-r)
				{
					temp1 =r;
					temp2 =n-r;
				}
				for(int i=1;i<=n;i++)
				{
					if(i<=temp2)
					{
						rfact = (rfact%MOD* i%MOD)%MOD;
						nrfact = (nrfact%MOD* i%MOD)%MOD;
					}
					else if(i<=temp1)
					{
						nrfact = (nrfact%MOD* i%MOD)%MOD;
					}
					nfact = (nfact%MOD* i%MOD)%MOD;
				}
				return nfact/(rfact*nrfact);
			}
		    public static long find_ncr(long n, long r) {
		    	long result=1;
		    	 //  System.out.println(factorial(29));
		    	   result = factorial(n)/(factorial(r)*factorial(n-r));
		    	   return result;
		    	}
		   public static long factorial(long n) {
		    	   long c;
		    	   long result = 1;
		    	 
		    	   for (c = 1; c <= n; c++)
		    	      result = result*c;
		    	 
		    	   return result;
		    	}
		    public static long power(long base, long exp) {
		        long res=1;
		        while(exp>0) {
		           if(exp%2==1) res=(res*base)%MOD;
		           base=(base*base)%MOD;
		           exp/=2;
		        }
		        return res%MOD;
		    }
	public static void computeLPSArray(String pat, int M, int lps[])
    {
        // length of the previous longest prefix suffix
        int len = 0;
        int i = 1;
        lps[0] = 0;  // lps[0] is always 0
 
        // the loop calculates lps[i] for i = 1 to M-1
        while (i < M)
        {
            if (pat.charAt(i) == pat.charAt(len))
            {
                len++;
                lps[i] = len;
                i++;
            }
            else  // (pat[i] != pat[len])
            {
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar 
                // to search step.
                if (len != 0)
                {
                    len = lps[len-1];
 
                    // Also, note that we do not increment
                    // i here
                }
                else  // if (len == 0)
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
	public static long power(long i)
	{
		long c=1;
		while(i>1)
		{
			c=((c%MOD)*(2%MOD))%MOD;
			i--;
		}
		return c;
	}
	public static long gcd(long p, long q) {
        if (q == 0) {
                return p;
        }
        return gcd(q, p % q);
}
	static int mid=-1;
	static int find(int arr[],int k,int f,int l)
	{
		if(f>l)
			return mid;
		mid=(f+l)/2;
		if(arr[mid]==k)
			return mid;
		if(arr[mid]<k)
		{
			f=mid;
			return find(arr,k,f,l);
		}
		else
		{
			l=mid;
			return find(arr,k,f,l);
		}
	}
	private static int[] nextIntArray(InputReader in,int n)	
	{
		int[] a=new int[n];
		for(int i=0;i<n;i++)
			a[i]=in.nextInt();
		return a;
	}
	public static double dis(double x1,double x2,double y1)
	{
		return Math.sqrt(((x1-x2)*(x1-x2))+(y1*y1));
	}
	private static String[] nextStringArray(InputReader in,int n)	
	{
		String[] a=new String[n];
		for(int i=0;i<n;i++)
			a[i]=in.next();
		return a;
	}
	private static void show(int[] a)
	{
		for(int i=0;i<a.length;i++)
			System.out.print(a[i]+" ");
		System.out.println();
	}
	private static void show2DArray(char[][] a)
	{
		for(int i=0;i<a.length;i++)
		{
			for(int j=0;j<a[0].length;j++)
				System.out.print(a[i][j]);
			System.out.println();
		}
	}
 static long fact(long x)
 {
	 long i=x,mul=1;
	 while(i>0)
	 {
		 mul=(mul%1000000007)*(i%1000000007)%1000000007;
		 i--;
	 }
	 return mul;
 }
 static class LengthComparator implements Comparator<String> {
	    public int compare(String arg0, String arg1) {
		// Use Integer.compare to compare the two Strings' lengths.
		return (arg0+arg1).compareTo(arg1+arg0);
	    }
	}
// static long output(ArrayList<Integer> h[],int j,boolean[] v)
// {
//	 int k;
//	 v[j]=true;
//	 sum++;
//	 for(k=0;k<h[j].size();k++)
//	 {
//		 if(v[h[j].get(k)]==false)
//		 {
//			 output(h,h[j].get(k),v);
//		 }
//	 }
//	 return sum;
// }
 static long func(boolean v[],int j,ArrayList<Integer> h[],long ban[])
 {
	 	v[j]=true;
	 	 int k;
	 	long sum=0;
	    sum=sum+ban[j];
	 	//System.out.println(h[j].size());
	 	for(k=0;k<h[j].size();k++)
	 	{
	 		if(v[h[j].get(k)]==false)
	 		{
	 			v[h[j].get(k)]=true;
	 			sum+=func(v,h[j].get(k),h,ban);
	 		}
	 	}
	 	return sum;
 }
/*static class Graph {
    	
    	private static Deque<Integer> stack = new ArrayDeque<Integer>();
 		private int least,count,v;
 		
		Set<Integer>[] cities;
    	private int[] risk;
    	
    	Graph(int n,String[] risk){
    		
    		cities = new HashSet[n];
    		this.risk = new int[n];
    		for(int i =0;i<n;i++){
    			cities[i] = new HashSet<>();
    		}
    		for(int i =0;i<n;i++){
    			this.risk[i] = Integer.parseInt(risk[i]);
    		}
    		visited = new boolean[n];
    	}
    	
    	
    	public void add(int x,int y){
    		cities[x].add(y);
    		cities[y].add(x);
    	}
}*/
	static int root(int arr[],int i)
	{
		while(arr[i]!=i)
		{
			i=arr[i];
		}
		return i;
	}
	static boolean find(int arr[],int a,int b)
	{
		if(root(arr,a)==root(arr,b))
		{
			return true;
		}
		else
			return false;
	}
	static void weighted_union(int arr[],int size[],int a,int b)
	{
		int root_a=root(arr,a);
		int root_b=root(arr,b);
		if(root_a!=root_b)
		{
			if(size[root_a]<size[root_b])
			{
				arr[root_a]=arr[root_b];
				size[root_b]+=size[root_a];
			}
			else
			{
				arr[root_b]=arr[root_a];
				size[root_a]+=size[root_b];
			}
		//	count--;
		}
	}
	static class Pair implements Comparable<Pair>
	{
		private long first;
		private long index;
		//private long second;;
 
		public Pair(long i, long j) 
		{ 
			this.first = i;
			this.index = j;
		}
		public Pair() {
			// TODO Auto-generated constructor stub
		}
		public long getFirst() { return first; }
		//public long getSecond() { return second; }
		public long getIndex() { return index ;}
		public void setFirst(long k) { this.first=k ; }
		public void setIndex(long k) { this.index=k ;}
		//public void setSecond(long k) { this.second=k ;}
		@Override
		public int compareTo(Pair o) 
		{
			return Long.compare(this.first, o.first);
		}
		
	}
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
 
		public InputReader(InputStream inputstream) {
			reader = new BufferedReader(new InputStreamReader(inputstream));
			tokenizer = null;
		}
 
		public String nextLine(){
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}