By Jorge Menezes, PUC Goiás Brazil
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 2n integers 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 |
1 |
20 20 |