#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return (b > 0) ? gcd(b, a % b) : a; }
long long mi[3] = {1, 0, -1};
struct f {
  long long a, b;
  void init(long long x, long long y) {
    a = x;
    b = y;
  }
  void show() { cout << a << "/" << b << endl; }
};
struct K {
  long long k;
  int i;
  long long h;
  void init(long long a, int b, long long c) {
    k = a;
    i = b;
    h = c;
  }
} s[3];
bool cmp(K a, K b) { return a.k < b.k || (a.k == b.k && a.h < b.h); }
long long habs(long long a) { return (a < 0) ? -a : a; }
void yue(f &a, long long b, long long c) {
  long long x = gcd(b, c);
  b = b / x;
  c = c / x;
  a.init(b, c);
}
int main() {
  long long x, y, n;
  cin >> x >> y >> n;
  long long gxy = gcd(x, y);
  y = y / gxy;
  x = x / gxy;
  if (y <= n)
    cout << x << "/" << y << endl;
  else {
    long long i;
    int j;
    f now, ans;
    f min;
    for (i = 1; i <= n; i++) {
      long long m = x * i / y;
      int cnt = 3;
      for (j = 0; j < 3; j++) {
        if (m + mi[j] < 0) cnt = 2;
        s[j].init(habs(x * i - y * (m + mi[j])), j, m + mi[j]);
      }
      sort(s, s + cnt, cmp);
      yue(now, s[0].k, y * i);
      if (i == 1) {
        min = now;
        yue(ans, m + mi[s[0].i], i);
      } else if (min.a * now.b > min.b * now.a) {
        min = now;
        yue(ans, m + mi[s[0].i], i);
      }
    }
    ans.show();
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction <image> whose denominator is no more than n. 

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value <image> is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.

Input

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 105).

Output

Print the required fraction in the format "a/b" (without quotes).

Examples

Input

3 7 6


Output

2/5


Input

7 2 4


Output

7/2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return (b > 0) ? gcd(b, a % b) : a; }
long long mi[3] = {1, 0, -1};
struct f {
  long long a, b;
  void init(long long x, long long y) {
    a = x;
    b = y;
  }
  void show() { cout << a << "/" << b << endl; }
};
struct K {
  long long k;
  int i;
  long long h;
  void init(long long a, int b, long long c) {
    k = a;
    i = b;
    h = c;
  }
} s[3];
bool cmp(K a, K b) { return a.k < b.k || (a.k == b.k && a.h < b.h); }
long long habs(long long a) { return (a < 0) ? -a : a; }
void yue(f &a, long long b, long long c) {
  long long x = gcd(b, c);
  b = b / x;
  c = c / x;
  a.init(b, c);
}
int main() {
  long long x, y, n;
  cin >> x >> y >> n;
  long long gxy = gcd(x, y);
  y = y / gxy;
  x = x / gxy;
  if (y <= n)
    cout << x << "/" << y << endl;
  else {
    long long i;
    int j;
    f now, ans;
    f min;
    for (i = 1; i <= n; i++) {
      long long m = x * i / y;
      int cnt = 3;
      for (j = 0; j < 3; j++) {
        if (m + mi[j] < 0) cnt = 2;
        s[j].init(habs(x * i - y * (m + mi[j])), j, m + mi[j]);
      }
      sort(s, s + cnt, cmp);
      yue(now, s[0].k, y * i);
      if (i == 1) {
        min = now;
        yue(ans, m + mi[s[0].i], i);
      } else if (min.a * now.b > min.b * now.a) {
        min = now;
        yue(ans, m + mi[s[0].i], i);
      }
    }
    ans.show();
  }
  return 0;
}

```