#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
bool isprime(unsigned long long n) {
  if (n < 2) return false;
  for (unsigned long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
unsigned long long bigmod(unsigned long long a, unsigned long long p,
                          unsigned long long m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    long long c = bigmod(a, p / 2, m);
    return ((c % m) * (c % m)) % m;
  } else
    return ((a % m) * bigmod(a, p - 1, m)) % m;
}
int k;
unsigned long long n;
set<unsigned long long> s, s1;
vector<unsigned long long> v;
int main() {
  ios_base ::sync_with_stdio(false);
  cin >> n >> k;
  if (isprime(n)) {
    if (k > 2) return cout << -1, 0;
    return (k == 1) ? cout << 1 : cout << n, 0;
  }
  for (unsigned long long i = 1; i * i <= n; i++) {
    if (n % i == 0) s.insert(i);
    if (n % (i * i) == 0) s.insert(i * i);
  }
  set<unsigned long long>::iterator it = s.begin();
  while (it != s.end()) {
    s1.insert(n / (*it));
    s1.insert(*it);
    it++;
  }
  set<unsigned long long>::iterator it1 = s1.begin();
  while (it1 != s1.end()) {
    v.push_back(*it1);
    it1++;
  }
  sort(v.begin(), v.end());
  if ((k - 1) >= v.size())
    cout << -1;
  else
    cout << v[k - 1];
  return 0;
}

### Prompt

Create a solution in CPP for the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
bool isprime(unsigned long long n) {
  if (n < 2) return false;
  for (unsigned long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
unsigned long long bigmod(unsigned long long a, unsigned long long p,
                          unsigned long long m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    long long c = bigmod(a, p / 2, m);
    return ((c % m) * (c % m)) % m;
  } else
    return ((a % m) * bigmod(a, p - 1, m)) % m;
}
int k;
unsigned long long n;
set<unsigned long long> s, s1;
vector<unsigned long long> v;
int main() {
  ios_base ::sync_with_stdio(false);
  cin >> n >> k;
  if (isprime(n)) {
    if (k > 2) return cout << -1, 0;
    return (k == 1) ? cout << 1 : cout << n, 0;
  }
  for (unsigned long long i = 1; i * i <= n; i++) {
    if (n % i == 0) s.insert(i);
    if (n % (i * i) == 0) s.insert(i * i);
  }
  set<unsigned long long>::iterator it = s.begin();
  while (it != s.end()) {
    s1.insert(n / (*it));
    s1.insert(*it);
    it++;
  }
  set<unsigned long long>::iterator it1 = s1.begin();
  while (it1 != s1.end()) {
    v.push_back(*it1);
    it1++;
  }
  sort(v.begin(), v.end());
  if ((k - 1) >= v.size())
    cout << -1;
  else
    cout << v[k - 1];
  return 0;
}

```