One day Joseph learned a very important sequence of n numbers. After thoroughly analyzing it, he found that it is an arithmetic progression. In order not to forget it, he wrote down the numbers on n cards.
But then there was a nuisance. His little brother Henry learned another important sequence of n numbers, and wrote on another n cards. After that, Henry mixed all 2n cards together.
Now Joseph wants to restore his sequence from these cards. Unfortunately this may be done several ways. But since Joseph does not remember the original sequence, any arithmetic progression is satisfactory.
Joseph does not want to do it manually, so he turns to your help. Recall that a sequence a1,a2,...,an is an arithmetic progression if there is a number d such that ai=ai-1+d for all i from 2 to n. The number d is called common difference.
Warn: 本題有 specialjudge
The input file consists multiple test cases, each on two lines. The first line of each test case contains an integer n (1<= n<=100000). The next line contains 2n integers, denoting the numbers written on the cards. The absolute value of every number is at most 109. It is guaranteed that it is always possible the choose n of the numbers to form an arithmetic progression.
For each test case please output one line, containing two integers, a1 and d, denoting the first element and the common difference of the arithmetic progression. If there are multiple solutions, you may output any one of them.
3 8 3 7 1 5 4
1 3
The sample output stands for the arithmetic progression 1,4,7.
Other acceptable outputs include "1 2", "3 1", "3 2",
"5 -1", "5 -2", "7 -2", and "7 -3".
Migrated from old NTUJ.
All-Russian Olympiad team programming 2010
| No. | Testdata Range | Score |
|---|