URI Online Judge | 3089

Christmas Gifts

By Jorge Menezes, PUC Goiás BR 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.


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.


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

10 10
10 5
40 39 20 1
1090 300 93 82 71 62 53 41

20 20
15 15
59 41
1131 153