Phân số gần nhất

Cho ba số nguyên dương $x$, $y$, $n$. Hãy tìm phân số $\frac{a}{b}$ gần với $\frac{x}{y}$ nhất trong số những phân số có mẫu số không vượt quá $n$.

Nói cách khác, cần tìm cặp số nguyên $a$, $b$ thoả mãn $1\le b\le n$ và $0\le a$ sao cho giá trị $|\frac{x}{y}-\frac{a}{b}|$ nhỏ nhất có thể.

Nếu có nhiều phân số cùng đạt khoảng cách nhỏ nhất, hãy chọn phân số có mẫu số nhỏ nhất. Nếu vẫn còn nhiều phân số, hãy chọn phân số có tử số nhỏ nhất. Phân số $\frac{a}{b}$ không nhất thiết phải ở dạng tối giản.

Dữ liệu vào

Một dòng duy nhất chứa ba số nguyên $x$, $y$, $n$.

Dữ liệu ra

In ra phân số cần tìm theo đúng định dạng a/b.

Ràng buộc

• $1\le x,y,n\le {10}^5$

Ví dụ