URI Online Judge | 3089

By Jorge Menezes, PUC Goiás Brazil

Timelimit: 1

Mrs. Ricota is a meticulous lady. As Christmas is coming she wants to distribute pairs of gifts to her family.

During her last trip, Mrs. Ricota bought 2n gifts for her n grandchildren. Each gift cost xi reais (1 ≤ i ≤ 2n) and, to avoid conflicts, she plans to organize the pairs of gift in a way that minimizes the difference between the total value of the most expensive pair of gifts and the total value of the cheapest pair.

As you are a kind person, Mrs. Ricota decided to ask your help to organize the gifts.

## Input

The input consists of several test cases. The first line of a test case has an integer n (2 ≤ n ≤ 104), the number of grandchildren. The second line has 2integers xi (1 ≤ xi ≤ 108, where 1 ≤ i ≤ 2n) in descending order and separated for exactly one whitespace. Each integer xi represents the value of the i-th gift bought by Mrs. Ricota.

The first line of the last test case contains n = 0 and must not be processed.

## Output

For each test case print a line with the total price of the most expensive pair of gifts and the total price of the cheapest pair of gifts separated by a blank space.

 Input Sample Output Sample 1 10 10 1 10 5 2 40 39 20 1 4 1090 300 93 82 71 62 53 41 0 20 20 15 15 59 41 1131 153