Gift for Luigi
InterviewTime limit2sMemory limit1024 MB
Given four stick lengths, find the two side lengths of the largest-area rectangle that can be cut from the sticks.
Statement
Mario wants to give Luigi a present. Mario has four sticks with positive integer lengths. He can break each stick into several other sticks. The length of each resulting stick must also be a positive integer, and the total length of the pieces must equal the length of the original stick.
After that, Mario picks four of the resulting sticks that can form a rectangle, using the chosen sticks as its sides. Each side must consist of exactly one chosen stick. Luigi loves rectangles with a large area, so Mario tries to get the rectangle with the largest possible area. Help him find such a rectangle.
Input
One line contains four positive integers , , , separated by spaces. These are the lengths of the sticks Mario originally had ().
Output
Print two integers separated by a space: the side lengths of the rectangle with the largest area that Mario can obtain by splitting the original sticks. If there are several answers, print any of them.
Hint
In the test from the statement, the optimal answer is obtained as follows. Split the second stick into sticks of lengths 2 and 6, keep the first and third sticks as they are, and split the fourth stick into three sticks of lengths 1, 9 and 9. Then take the sticks of lengths 6, 6, 9 and 9. They form a rectangle with side lengths 6 and 9, and its area is optimal for this test.