Multiple of N (1)

Interview

Time limit2sMemory limit512 MB

Summary
Given 2N-1 numbers, find N of them whose sum is divisible by N, or report that none exists.
Level

Medium6 of 10

Topics
Combinatorics, Prefix sum, Math, Greedy
Solved
No attempts yet

Problem

You are given 2N−12N-1 numbers. Among them, find NN numbers whose sum is divisible by NN.

Input

The first line gives NN. (1≤N≤5001 \le N \le 500)

The second line gives 2N−12N-1 numbers between 00 and N−1N-1 inclusive, separated by spaces.

Output

On the first line, print the NN numbers satisfying the condition, separated by spaces.

If several such sets exist, printing any one of them is accepted. The order of the printed numbers does not matter.

If no set of numbers satisfies the condition, print -1.

Examples1

  1. Example 1

    Input
    4
    1 2 3 0 1 2 3
    
    Expected output
    1 1 3 3