Fractions

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.

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

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.

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