MicroRNA Ranking

Time limit2sMemory limit512 MB

Summary

Given k permutations of n items, find a permutation where every earlier item beats the later one in at least half the rankings, choosing the lexicographically smallest such permutation.

Level: Medium7 of 10
Topics: Graph, Topological sort, Sorting, Greedy
Solved: No attempts yet

Problem

Ahlaam studies computer science and is writing her master's thesis on a bioinformatics project about microRNAs, a class of molecules found in cells. She wants to find the microRNAs that are relevant to one health factor in humans.

Ahlaam has designed $k$ microRNA ranking algorithms. Each algorithm ranks the microRNAs from its own point of view. There are $n$ microRNAs numbered $1$ through $n$ , and each algorithm prints one permutation of them. In the permutation printed by an algorithm, the first microRNA is the one that algorithm considers most relevant to the health factor, and the last one is the least relevant.

Ahlaam wants to report a consensus ranking. In a consensus ranking, if microRNA $i$ is placed before microRNA $j$ , then at least half of the algorithms must rank $i$ before $j$ . Write a program that helps Ahlaam find a consensus ranking.

Input

The input holds several test cases. The first line of each test case has two integers $n$ and $k$ separated by a space, the number of microRNAs and the number of ranking algorithms ( $1 \le n \le 1000$ , $1 \le k \le 200$ ).

Each of the next $k$ lines holds a permutation of the numbers $1$ through $n$ . The $i$ -th of those lines is the output of the $i$ -th ranking algorithm.

The last line of the input is 0 0. Do not process that line.

Output

For each test case, print one line holding a permutation of the numbers $1$ through $n$ that is a consensus ranking. Separate the numbers with single spaces.

If more than one consensus ranking exists, print the lexicographically smallest one. A sequence $a_1, \dots, a_n$ is lexicographically smaller than a sequence $b_1, \dots, b_n$ if there is a positive integer $j$ such that $a_i = b_i$ for all $1 \le i \le j - 1$ and $a_j < b_j$ .

If no consensus ranking exists, print No solution instead.

Examples2

Example 1

Input

Expected output

2 4 1 5 3
1 2 3 4 5
No solution

Example 2
Input
```
5 2
3 1 2 4 5
3 2 1 5 4
0 0
```
Expected output
```
3 1 2 4 5
```