Dishonest Lottery

Interview

Time limit1sMemory limit1024 MB

Summary

Given 10n drawings of five distinct numbers from 1 to 50, list every number that appears more than 2n times, or print -1 if none do.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

You suspect your local lottery of cheating! Some numbers are coming up too often!

Each week, the lottery randomly selects five numbers in the range from one to fifty. So, each number should appear about $10\%$ of the time if the numbers are truly chosen randomly. If a number appears far more than that, it is suspicious.

Determine whether a set of lottery drawings is suspicious by listing all numbers that appear too often. To allow for random error, flag any number that appears more than $20\%$ of the time.

Input

The first line contains a single integer $n$ ( $1 \le n \le 1000$ ). There will be $10 \cdot n$ lottery results to analyze.

Each of the next $10 \cdot n$ lines contains $5$ integers $x$ ( $1 \le x \le 50$ ). Each line represents one drawing. All values on a line are unique.

Output

On a single line, output all numbers that appear strictly more than $2 \cdot n$ times in the list. If there is more than one, output them separated by spaces, in sorted order from smallest to largest. If there are none, output $-1$ .

Examples1

Example 1

Input

1
32 30 16 45 27
34 45 35 31 42
1 12 26 50 13
34 50 36 21 39
47 7 41 18 45
28 48 2 8 4
16 40 17 2 19
50 4 30 15 6
31 13 33 46 18
49 23 24 17 48

Expected output

45 50