Gathering Search Results

Interview

Time limit3sMemory limit1024 MB

Summary

Given k search engine rankings of n results, output one combined ranking that minimizes the sum of squared position differences across all engines.

Level: Medium5 of 10
Topics: Sorting, Greedy, Math
Solved: No attempts yet

Problem

You are making a new search engine for algorithms, called the Benelux Algorithm Preview Collector. All the marketing has been done, and you have plenty of investors, but you have not written any code yet. With only five hours left until the product launch, there is not enough time to implement your own ranking algorithm. Instead, whenever a user searches for an algorithm, you forward the search to the $k$ most popular other search engines and use their results.

Each of these $k$ search engines gives a list of $n$ results, ordered by estimated relevance. For every search term you try, the search engines always return the same $n$ results, and only the order differs between them. You need to combine the $k$ rankings into a single ranking.

Give each possible combined ranking a cost. For each result $r$ and search engine $s$ , if your combined ranking puts $r$ at position $i$ and search engine $s$ puts $r$ at position $j$ , the cost is $(i-j)^2$ . The total cost of a combined ranking is the sum of all $k \cdot n$ costs.

As an example, consider the second sample case. The first search engine returns the same result as the sample output, which has cost $0$ . The second search engine swaps two adjacent results, which has cost $1+1=2$ . For the third search engine, the first result moves two positions back, and the other two shift one position to the front, which has cost $4+1+1=6$ . The total cost is $0+2+6=8$ , which is the minimal possible cost over all possible orders.

What is the order in which BAPC should output the results, such that the total cost is minimized?

Input

The input consists of:

One line containing two integers $n$ and $k$ ( $1\leq n\leq 5000$ , $1\leq k\leq 100$ ), the number of results and the number of search engines.
$k$ lines, each containing $n$ integers, denoting the results as ordered by one of the search engines. Each line contains every integer from $1$ to $n$ exactly once.

Output

Output the combined order of the results, such that the cost is minimized.

If there are multiple valid solutions, you may output any one of them.

Examples3

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