Number Selection Game

Time limit2sMemory limit128 MB

Summary

Given 2N-1 integers where N is a power of two, select exactly N of them whose sum is divisible by N, using a doubling construction.

Level: Hard8 of 10
Topics: Divide and conquer, Math, Combinatorics, Greedy
Solved: No attempts yet

Problem

You are given an integer $N$ such that $N = 2^k$ and $1 \le k \le 10$ . Then $2N - 1$ integers are given.

Choose exactly $N$ of the given numbers so that the sum of the chosen numbers is divisible by $N$ . Print the chosen $N$ numbers. If several answers are possible, print any one of them.

Input

The first line contains $N$ .

The second line contains $2N - 1$ integers. Each integer is between $0$ and $1000$ , inclusive.

Output

On the first line, print $N$ numbers separated by spaces whose sum is divisible by $N$ .

If several answers are possible, print any one of them. If no such selection exists, print -1.

Examples1

Example 1
Input
```
4
1 2 3 4 5 6 7
```
Expected output
```
1 3 5 7
```