Problem Description

To verify a newly proposed conjecture, physicist Little I needs to complete $n$ types of physics experiments. The importance of experiment type $i \ (1 \le i \le n)$ is $2^{-i}$. Each type of experiment only needs to be done once. Little I can only do one experiment at a time, and once an experiment is started, they cannot switch to another one halfway. That is, without any other restrictions, the order in which Little I completes the experiments can be represented by a permutation of $1$ to $n$.

However, things do not go smoothly. There are $m$ rounds of cosmic rays, which will strike the experimental base after Little I has completed $a_1$ types, $a_2$ types, $\dots$, $a_m$ types (note: not experiment type $a_i$) of experiments. It is guaranteed that $1 \le a_1 < a_2 < \dots < a_m < n-m$. Therefore, Little I needs to carefully arrange the order of experiments.

In round $j \ (1 \le j \le m)$, the cosmic rays will interfere with the apparatus of exactly one experiment type. The interfered experiment type is determined as follows:

• A permutation $p_{j,1},\dots,p_{j,n}$ of $1$ to $n$ is given, where appearing earlier means that experiment type $i$ is more vulnerable to this round of cosmic rays. The permutations given for different rounds are not necessarily the same.
• When this round of cosmic rays hits the base, among all experiment types that are currently not completed and not yet interfered, the most vulnerable one will be interfered with, and the corresponding experiment can no longer be performed afterward.

Under these conditions, Little I can complete a total of $(n-m)$ experiment types. Little I wants the sum of their importance to be as large as possible, but Little I is a physicist and does not understand algorithms, so Little I asks you for help. You need to provide a valid experiment order such that the completed $(n-m)$ experiment types are all not interfered with by cosmic rays, and the sum of importance is maximized.

Input Format

The first line contains two positive integers $n,m$, representing the number of experiment types and the number of cosmic ray rounds.

The next line contains $m$ integers $a_1,a_2,\dots,a_m$, meaning after how many experiment types are completed each round of cosmic rays strikes the base.

The next $m$ lines each contain $n$ integers $p_1,p_2,\dots,p_n$, describing the vulnerability ranking for each round in order. It is guaranteed that $1 \le p_i \le n$ and each line forms a permutation of $1$ to $n$.

Output Format

Output one line with $n-m$ integers, representing the experiment order you give. You need to ensure that when each experiment type is performed, it has not been interfered with by cosmic rays, and the sum of importance is maximized. If there are multiple solutions, output any one of them.

3 1
1
1 2 3

1 3

3 1
1
2 3 1

2 1

6 2
1 3
3 2 4 5 6 1
5 4 1 3 6 2

1 4 5 2

Hint

[Sample Explanation #1]

After Little I completes the first experiment type for the first time, the cosmic rays will strike the apparatus of the second experiment type, so the second time Little I can only complete the third experiment type. It is easy to prove that this plan achieves the maximum total importance.

[Sample Explanation #2]

In this sample, if Little I completes the first experiment type the first time, then the cosmic rays will strike the apparatus of the second experiment type, causing the second time Little I can only complete the third experiment type. In this case, the total importance is $0.625$, while the plan given by the sample output has total importance $0.75$.

[Sample Explanation #3]

For this sample, there are multiple valid outputs, such as 5 4 1 2, which is also a valid answer.

[Constraints]

For all testdata, $3 \le n \le 600$, $1 \le m \le \lfloor \frac{n-1}{2} \rfloor$, $1 \le a_1 < a_2 < \dots < a_m < n-m$.

[Source]

From the 2023 Tsinghua University Student Algorithm Competition and University Invitational (THUPC2023) Finals.

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023.

Translated by ChatGPT 5