Candies for first graders

Interview

Time limit1sMemory limit1024 MB

Summary

Given n, a, and b, find how many candies Andrei and Anya each buy so the total leaves the smallest remainder mod n, with ties going to the largest x.

Level: Medium4 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

Andrei and Anya, two high school students, plan to attend the September 1 celebration for first graders. They want to bring candies to hand out. There will be $n$ first graders at the celebration. Each high schooler is willing to buy between $a$ and $b$ candies, inclusive.

They want the total number of candies to be divisible evenly among all first graders. If that is not possible, they want as few candies as possible left over after splitting evenly. If several purchases give the same result, they choose the one where Andrei buys the most candies. If there are still several options, they choose the one where Anya buys the most candies.

Find how many candies each of them should buy.

Input

Three positive integers are given, one per line: $n$ is the number of first graders, and $a$ and $b$ are the minimum and maximum number of candies each high schooler is willing to buy ( $1 \le n \le 10^9$ , $1 \le a \le b \le 10^9$ ).

Output

Print two integers $x$ and $y$ , the number of candies Andrei and Anya buy, respectively.

Examples1

Example 1
Input
```
2
6
7
```
Expected output
```
7 7
```