Fractification

Interview

Time limit2sMemory limit512 MB

Summary

Given four positive integers, arrange them into two fractions a/b + c/d so the sum is as small as possible, and print the arrangement.

Level: Medium4 of 10
Topics: Greedy, Sorting, Math, Brute force
Solved: No attempts yet

Problem

Little children love to break their toys so much! Little Andrew is no exception: he breaks everything he sees into fragments. This time he is about to break a set of four positive integers.

Let the fractification of four integers ( $a$ , $b$ , $c$ , $d$ ) be the sum $\frac{a}{b} + \frac{c}{d}$ Little Andrew doesn't like anything larger than himself, so he wants the fractification to be as small as possible.

Help Andrew make the fractification of the given four integers as small as possible. You may swap these integers with each other in any way you want.

Input

The first and only line of input contains four positive integers $a$ , $b$ , $c$ , $d$ separated by spaces ( $1 \le a, b, c, d \le 10^9$ ).

Output

Print four integers that are a permutation of the given four such that their fractification is as small as possible. If more than one such permutation exists, print any of them.

Notes

In the first example, the output permutation gives $\frac{1}{3} + \frac{2}{4} = \frac{5}{6}$ which is minimal.

In the second example, the only possible output gives $\frac{5}{5} + \frac{5}{5} = 2$

Examples2

Example 1
Input
```
1 2 3 4
```
Expected output
```
1 3 2 4
```
Example 2
Input
```
5 5 5 5
```
Expected output
```
5 5 5 5
```