407908: GYM102939 F Factory Batching

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Factory Batchingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The AI Jeff has been created to help manage the packaging of Skittles! In fact, he was designed to be so intelligent that the overall management of deciding the packaging of skittles has become under his control.

Jeff's first task is given the $$$n$$$ skittles that are currently available, split them up into two batches, with the first batch containing $$$k$$$ skittles, and the second containing $$$n - k$$$ skittles. The first batch of skittles will be packaged and shipped out in a week, while the remaining skittles will be packaged in a month or so.

Jeff decides that he wants to rework the skittles packaging system in a way to optimize something. The only rules here are that no skittle can be wasted, and every package must have the same number of skittles. Since it is well known that every skittles bag must have the same number of skittles $$$s$$$, he decides given $$$k$$$ and $$$n - k$$$, $$$s$$$ will be the largest possible number of skittles such that $$$s$$$ divides both $$$k$$$ and $$$n - k$$$.

Jeff wants to find the optimal $$$k$$$ to maximize his skittle bag size. Unfortunately, Jeff has been stumped. Please help him determine the optimal batch size such that the packages will have the most skittles!

Input

The first and only line of input will contain $$$n (2 \le n \le 10^9)$$$, the number of skittles Jeff has.

Output

Output two space separated integers the batch sizes of skittles. If there are multiple ways to maximize the number of skittles in a package, output the answer that would be lexicographically the smallest (minimize the size of the first batch).

ExampleInput
15
Output
5 10

加入题单

上一题 下一题 算法标签: