Fractions

Time limit2sMemory limit128 MB

Summary

Given a fraction a/b and a bound c, find fractions a1/b1 <= a/b <= a2/b2 with denominators at most c that minimize a2/b2 - a1/b1.

Level: Hard8 of 10
Topics: Number theory, Math, Binary search, Recursion
Solved: No attempts yet

Problem

A rational number is usually written as a fraction. In a fraction a/b, a is the numerator and b is the denominator, and both are integers. When the denominator is very large, the fraction can be inconvenient to handle in formulas. Instead of using such a fraction a/b directly, we want to bracket it with two fractions a1/b1 and a2/b2 whose denominators are at most c.

The two fractions must satisfy a1/b1 <= a/b <= a2/b2. Call such two fractions an approximation pair for a/b. Among all possible pairs, find one that minimizes a2/b2 - a1/b1.

Input

The first line contains three integers a, b, and c.

Output

Print four integers a1, b1, a2, and b2 on the first line. The fractions a1/b1 and a2/b2 must be an approximation pair for the given fraction with the minimum possible difference. Also, a1 and b1 must be coprime, and a2 and b2 must be coprime. A fraction whose value is 0 must always be printed as 0 1.

Constraints

0 <= a < b <= 2 * 10^9
1 <= c <= 2 * 10^9

Examples1

Example 1
Input
```
3 7 4
```
Expected output
```
1 3 1 2
```