#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a, b, l, x, y;
    double minn = 10000000;
    cin >> a >> b >> l;
    for (int i = 1; i <= l; ++i)
        for (int j = 1; j <= l; ++j) {
            if (__gcd(i,j) == 1 && i * 1.0 / j - a * 1.0 / b >= 0 && i * 1.0 / j - a * 1.0 / b <= minn) {
                minn = i * 1.0 / j - a * 1.0 / b, x = i, y = j;
            }
        }
    cout << x << ' ' << y;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int md = 10007;
int qpow(int a, int b) {
  a %= md;
  int res = 1 % md;
  while (b) {
    if (b & 1) res = res * a % md;
    a = a * a % md;
    b >>= 1;
  }
  return res;
}
int main() {
  int a, b, k, n, m;
  cin >> a >> b >> k >> n >> m;
  int res = qpow(a, n) * qpow(b, m) % md;
  for (int i = 1, j = k; i <= n; ++i, --j) {
    res = res * j % md;
    res = res * qpow(i, md - 2) % md;
  }
  cout << res;
  return 0;
}

#include <iostream>
using namespace std;
bool b[1059];
int main() {
  int n, tmp, i, m = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> tmp;
    if (b[tmp] == false) ++m;
    b[tmp] = true;
  }
  cout << m << endl;
  for (i = 1; i < 1001; ++i)
    if (b[i] != 0)
      cout << i << ' ';
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
  int mx = 0, answer = 0;
  for (int i = 1; i <= 7; ++i) {
    int a, b;
    cin >> a >> b;
    if (a + b > mx && a + b > 8) {
      answer = i;
      mx = a + b;
    }
  }
  cout << answer;
  return 0;
}

#include <iostream>
using namespace std;
const int MAXN = 350 + 5;
int N, M;
int A[MAXN];
int card_each[5];
int F[45][45][45][45];
int main() {
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    for (int i = 1; i <= M; ++i) {
        int tmp; cin >> tmp;
        card_each[tmp]++;
    }
    F[0][0][0][0] = A[1];
    for (int a = 0; a <= card_each[1]; ++a)
    for (int b = 0; b <= card_each[2]; ++b)
    for (int c = 0; c <= card_each[3]; ++c)
    for (int d = 0; d <= card_each[4]; ++d) {
        int nxt = 1 + a + b * 2 + c * 3 + d * 4;
        if (a) F[a][b][c][d] = max(F[a][b][c][d], F[a - 1][b][c][d] + A[nxt]);
        if (b) F[a][b][c][d] = max(F[a][b][c][d], F[a][b - 1][c][d] + A[nxt]);
        if (c) F[a][b][c][d] = max(F[a][b][c][d], F[a][b][c - 1][d] + A[nxt]);
        if (d) F[a][b][c][d] = max(F[a][b][c][d], F[a][b][c][d - 1] + A[nxt]);
    }
    cout << F[card_each[1]][card_each[2]][card_each[3]][card_each[4]];
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, s[N], a[N], d[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) cin >> d[i];
  for (int i = 2; i <= n; ++i) {
    cin >> s[i];
    s[i] += s[i - 1];
  }
  int T;
  cin >> T;
  int mx = 0;
  for (int i = 1; i <= n && s[i] <= T; ++i) {
    priority_queue<PII> q;
    for (int j = 1; j <= i; ++j) q.push({a[j], d[j]});
    int res = 0;
    for (int j = 1; j <= T - s[i]; ++j) {
      PII p = q.top();
      q.pop();
      if (p.first <= 0) break;
      res += p.first;
      p.first -= p.second;
      q.push(p);
    }
    mx = max(mx, res);
  }
  cout << mx << endl;
  return 0;
}

#include<iostream>
using namespace std;
int main()
{
    int a[11],p,i,sum=0;
    for(i=1;i<=10;i++)
        cin>>a[i];
    cin>>p;
    for(i=1;i<=10;i++)
        if(30+p>=a[i])
            sum++;
    cout<<sum;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct Node {
  int a, b, c;
  inline friend bool operator < (const Node &a, const Node &b) {
    return a.c > b.c;
  }
} a[N];
int n, m, f[N];
int find(int x) {
  if (f[x] == x)
    return x;
  return f[x] = find(f[x]);
}
signed main() {
  // freopen("awa.in", "r", stdin);
  // freopen("awa.out", "w", stdout);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i)
    cin >> a[i].a >> a[i].b >> a[i].c;
  for (int i = 1; i <= n * 2; ++i)
    f[i] = i;
  sort(a + 1, a + m + 1);
  for (int i = 1; i <= m; ++i) {
    int t1 = find(a[i].a), t2 = find(a[i].b);
    if (t1 == t2) { printf("%d", a[i].c); return 0; }
    f[t2] = find(a[i].a + n);
    f[t1] = find(a[i].b + n);
  }
  cout << 0;
  return 0;
}

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
using namespace std;
stack<int>st;
char ch;
long long x;
inline int read()
{
  ch=getchar(),x=0;
  while(isdigit(ch)){x=x*10+ch-'0',ch=getchar();}
  return x;
}
int main()
{
  int k=read(),n=read();
  while(n){
    st.push(n&1);
    n>>=1;
  }
  x=0;
  while(!st.empty())
    x+=st.top()*pow(k,st.size()-1),st.pop();
  printf("%lld", x);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m;
int r[N], c[N], now;
int d[N], s[N], t[N];
inline bool ok(int x) {
  if (now > x) {
    for (int i = x + 1; i <= now; ++i) {
      c[s[i]] -= d[i];
      c[t[i] + 1] += d[i];
    }
  } else {
    for (int i = now + 1; i <= x; ++i) {
      c[s[i]] += d[i];
      c[t[i] + 1] -= d[i];
    }
  }
  now = x;
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum += c[i];
    if (sum > r[i]) return 1;
  }
  return 0;
}
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 1) + (x << 3) + (ch & 15);
    ch = getchar();
  }
  return x * f;
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; ++i) r[i] = read();
  for (int i = 1; i <= m; ++i) {
    d[i] = read();
    s[i] = read();
    t[i] = read();
  }
  int l = 1, r = m;
  bool oo = 0;
  while (l < r) {
    int mid = l + r >> 1;
    if (ok(mid)) oo = 1, r = mid;
    else l = mid + 1;
  }
  if (oo) {
    cout << -1 << endl;
    cout << l;
  } else {
    puts("0");
  }
  return 0;
}