Under construction

Still being built. Things may change

Gift for Luigi

Interview

Time limit2sMemory limit1024 MB

Summary
Given four stick lengths, find the two side lengths of the largest-area rectangle that can be cut from the sticks.
Level

Medium4 of 10

Topics
Sorting, Greedy
Solved
No attempts yet

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 aa, bb, cc, dd separated by spaces. These are the lengths of the sticks Mario originally had (1≤a,b,c,d≤10151 \le a, b, c, d \le 10^{15}).

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.

Examples1

  1. Example 1

    Input
    1 8 6 19
    
    Expected output
    9 6