Boris and Berta

Interview

Time limit2sMemory limit512 MB

Summary

Given a target distance n and lengths m and c, find non-negative counts of miles and cables whose total length is as close to n as possible.

Level: Medium4 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Boris is making a quest for his sister Berta. One of the tasks is to find a point on the map that is $n$ meters north of their house. But it is too easy if $n$ is given directly. Boris decided to specify the distance using miles and cables.

He found out that miles vary a lot: from a $500$ -meter Chinese mile (called li) up to an $11\,299$ -meter Norwegian mile (called mil). A cable length can be anywhere from $169$ to $220$ meters.

Boris decided to use an $m$ -meter mile and a $c$ -meter cable. Now he wants to write the $n$ -meter distance as " $M$ miles and $C$ cables" with non-negative integers $M$ and $C$ as precisely as possible, that is, he wants to minimize $|M\cdot m+C\cdot c-n|$ . Help him!

Input

Three lines contain an integer each: $n$ , the distance to represent, $m$ , the chosen length of a mile, and $c$ , the chosen length of a cable ( $1 \le n \le 10^9$ ; $500 \le m \le 11\,299$ ; $169 \le c \le 220$ ). All values are given in meters.

Output

Print two non-negative integers $M$ and $C$ , the best approximation of the distance of $n$ meters using the chosen mile and cable lengths. If there are multiple best approximations, print any of them.

Hint

The second example test has two correct answers: "1 6" and "3 1".

Examples2

Example 1
Input
```
1234
500
169
```
Expected output
```
0 7
```
Example 2
Input
```
1700
500
200
```
Expected output
```
1 6
```