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.*;

public class cd392q1 {



public static void main(String[] args) {

in=new InputReader(System.in);
w=new PrintWriter(System.out);

long n=in.nextLong();
long k=in.nextLong();
long count=0;
int p=0;
int q=0;
long a[]=new long[10000000];
long b[]=new long[10000000];
for (long i=1; i<=(long)(Math.sqrt(n)); i++)
{
if (n%i==0)
{
if (n/i == i)
{a[p++]=i;}
else
{


a[p++]=i;
b[q++]=n/i;
}
}
}
//System.out.println(p+" "+q);
if(k>p+q)
{
System.out.println("-1");
System.exit(0);
}
for(int i=0;i<p;i++)
{
count++;
if(count==k)
{
System.out.println(a[i]);
System.exit(0);
}
}
for(int i=q-1;i>=0;i--)
{
count++;
if(count==k)
{
System.out.println(b[i]);
System.exit(0);
}
}



}

static InputReader in;
static PrintWriter w;
static class Pair implements Comparable<Pair> {
int u;
int v;
int z;
public Pair(){

}
public Pair(int u, int v) {
this.u = u;
this.v = v;
}

public int hashCode() {
int hu = (int) (u ^ (u >>> 32));
int hv = (int) (v ^ (v >>> 32));
return 31*hu + hv;
}

public boolean equals(Object o) {
Pair other = (Pair) o;
return (u == other.u && v == other.v);
}

public int compareTo(Pair other) {
return Integer.compare(u, other.u) != 0 ? (Integer.compare(u, other.u)) : (Integer.compare(v, other.v));
}

public String toString() {
return "[u=" + u + ", v=" + v + "]";
}
}

public static void debug(Object... o) {
System.out.println(Arrays.deepToString(o));
}

public static String rev(String s)
{
StringBuilder sb=new StringBuilder(s);
sb.reverse();
return sb.toString();
}

static long lcm(long a, long b)
{
return a * (b / gcd(a, b));
}

static long gcd(long a, long b)
{
while (b > 0)
{
long temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}

public static long max(long x, long y, long z){
if(x>=y && x>=z) return x;
if(y>=x && y>=z) return y;
return z;
}
static int[] sieve(int n,int[] arr)
{
for(int i=2;i*i<=n;i++)
{
if(arr[i]==0)
{
for(int j=i*2;j<=n;j+=i)
arr[j]=1;
}
}
return arr;
}




static class InputReader {

private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
private SpaceCharFilter filter;

public InputReader(InputStream stream) {
this.stream = stream;
}

public int snext() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}

public int nextInt() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}

public long nextLong() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = snext();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = snext();
} while (!isSpaceChar(c));
return res * sgn;
}

public int[] nextIntArray(int n) {
return nextIntArray(n, 0);
}

public int[] nextIntArray(int n, int off) {
int[] arr = new int[n + off];
for (int i = 0; i < n; i++) {
arr[i + off] = nextInt();
}
return arr;
}

public long[] nextLongArray(int n) {
return nextLongArray(n, 0);
}

public long[] nextLongArray(int n, int off) {
long[] arr = new long[n + off];
for (int i = 0; i < n; i++) {
arr[i + off] = nextLong();
}
return arr;
}


public String readString() {
int c = snext();
while (isSpaceChar(c)) {
c = snext();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isSpaceChar(c));
return res.toString();
}

public String nextLine() {
int c = snext();
while (isSpaceChar(c))
c = snext();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = snext();
} while (!isEndOfLine(c));
return res.toString();
}

public boolean isSpaceChar(int c) {
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}

public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}


}