Problem Description

Jiahai has N baskets of apples, with the ith basket having a total of Ai apples. Since Jiahai is very neat, it is guaranteed that A is in non-decreasing order.

He wishes to merge a certain subset of these baskets into a larger container. He records down a sorted list of the total number of apples he will get for all possible subsets of baskets.

However, a gust of wind hit and blew all of Jiahai's baskets away (but not his paper, somehow). Help Jiahai recover his original array A.

Limits

Subtask 1 (11%): 1 ≤ N ≤ 2, 0 ≤ Ai ≤ 105.

Subtask 2 (13%): 1 ≤ N ≤ 4, 0 ≤ Ai ≤ 105.

Subtask 3 (7%): 1 ≤ N ≤ 20, 0 ≤ Ai ≤ 1.

Subtask 4 (22%): 1 ≤ N ≤ 20, 0 ≤ Ai ≤ 105, there will only be at most two unique values of Ai.

Subtask 5 (47%): 1 ≤ N ≤ 20, 0 ≤ Ai ≤ 105.

Subtask 6 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain 2N integers, representing the sorted list of numbers Jiahai recorded.

Output

The output should contain N lines, with each line containing one integer, representing the original array A.

Sample Testcase 1

Input

3
0 1 5 6 6 7 11 12

Output

1
5
6

Sample Testcase 2

Input

3
0 3 4 5 7 8 9 12

Output

3
4
5