A. Arranging Teams
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the coach of a competitive programming team with $$$n$$$ members. After months of intense training, your team is ready for the "Annual International Coding Pageant" (AICP). In this tournament, teams compete against each other in a series of one-on-one matches.

The tournament structure is peculiar. There are $$$m$$$ other teams, and your team will play against each of them. For every match against an opponent team, the players are lined up, and the $$$i$$$-th player from your team competes against the $$$i$$$-th player from the opponent's team.

Each of your team members has a known strength value. The opponent teams have already submitted their player arrangements, and these are fixed. Your task is to find a single, optimal arrangement for your own team members that will be used against all m opponent teams to maximize your total score across the entire tournament.

You have a team of $$$n$$$ members with strengths given by an array of size $$$n$$$. You are competing against $$$m$$$ other teams. The $$$k$$$-th opponent team (for $$$k$$$ from $$$1$$$ to $$$m$$$) also has $$$n$$$ members, with strengths given by $$$b_{k,1}, b_{k,2}, ..., b_{k,n}$$$.

You need to find a permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n$$$. This permutation $$$p$$$ will be your team's final arrangement for all matches. When your team (arranged as $$$p$$$) competes against opponent team $$$k$$$, your player at position $$$i$$$ (with strength $$$a_{p_i}$$$) is matched against their player at position $$$i$$$ (with strength $$$b_{k,i}$$$).

The outcome of an individual competition between a player of strength $$$s_1$$$ and a player of strength $$$s_2$$$ is determined as follows:

  • If $$$s_1 \gt s_2$$$, you win and get $$$1$$$ point.
  • If $$$s_1 = s_2$$$, it's a draw, and you get $$$0.5$$$ points.
  • If $$$s_1 \lt s_2$$$, you lose and get $$$0$$$ points.

Your team's total score is the sum of points from all individual competitions. That is, the sum of scores for each of your $$$n$$$ players against their counterparts in all $$$m$$$ opponent teams.

Your goal is to find the arrangement $$$p$$$ that maximizes this total score.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The first line contains two integers, $$$n$$$ ($$$1 \le n \le 20$$$) and $$$m$$$ ($$$1 \le m \le 5\,000$$$), the number of members per team and the number of opponent teams.

The second line contains n space-separated integers $$$a_1, a_2, ..., a_n$$$, representing the strengths of your team members ($$$1 \le a_i \le 10^9$$$).

The next $$$m$$$ lines each contain n space-separated integers. The $$$k$$$-th of these lines represents the strengths of the $$$k$$$-th opponent team: $$$b_{k,1}, b_{k,2}, ..., b_{k,n}$$$ ($$$1 \le b_{k,i} \le 10^9$$$).

Output

Print a single line containing $$$n$$$ space-separated integers, representing the optimal arrangement of your team's strengths that maximizes the total score. If multiple optimal arrangements exist, any one of them will be accepted.

Formally, let $$$p$$$ be the optimal permutation, you must output $$$a_{p_1},a_{p_2},\dots,a_{p_n}$$$ separated by whitespace in a single line.

Example
Input
2 2
10 20
15 5
12 18
Output
20 10
Note

Your team has strengths $$$[10, 20]$$$. There are two opposing teams.

  • Opponent 1: $$$[15, 5]$$$
  • Opponent 2: $$$[12, 18]$$$
Let's analyze the positions:
  • Position 1: Your player here will face opponents with strengths $$$[15, 12]$$$.
  • Position 2: Your player here will face opponents with strengths $$$[5, 18]$$$.

    If you use the arrangement $$$p=[1,2]$$$, the strength of the team is $$$[10, 20]$$$:

    • Player at Position 1 (strength $$$10$$$):
      • vs $$$15$$$: Lose ($$$0$$$ pts)
      • vs $$$12$$$: Lose ($$$0$$$ pts)
      • Position 1 Score: $$$0$$$ pts
    • Player at Position 2 (strength $$$20$$$):
      • vs $$$5$$$: Win ($$$1$$$ pt)
      • vs $$$18$$$: Win ($$$1$$$ pt)
      • Position 2 Score: $$$2$$$ pts
    • Total Score: $$$0 + 2 = 2$$$ pts

    If you use the arrangement $$$p=[2,1]$$$, the strength of the team is $$$[20, 10]$$$:

    • Player at Position 1 (strength $$$20$$$):
      • vs $$$15$$$: Win ($$$1$$$ pt)
      • vs $$$12$$$: Win ($$$1$$$ pt)
      • Position 1 Score: $$$2$$$ pts
    • Player at Position 2 (strength $$$10$$$):
      • vs $$$5$$$: Win ($$$1$$$ pt)
      • vs $$$18$$$: Lose ($$$0$$$ pts)
      • Position 2 Score: $$$1$$$ pt
    • Total Score: $$$2 + 1 = 3$$$ pts

The arrangement $$$[20, 10]$$$ yields a higher total score and is the optimal answer.