Problem Description

To verify a newly proposed conjecture, physicist Xiao I needs to complete $n$ types of physics experiments, where the importance of the $i$-th ($1 \le i \le n$) experiment is $2^{-i}$. Each experiment needs to be completed only once. Xiao I can only conduct one experiment at a time and cannot switch to another experiment halfway through, meaning that, in the absence of any other constraints, the order in which Xiao 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, each hitting the experimental base after Xiao I has completed $a_1$, $a_2$, $\dots$, $a_m$ experiments (note, not the $a_i$-th experiment), respectively, with $1 \le a_1 < a_2 < \dots < a_m < n-m$. Therefore, Xiao I needs to carefully arrange the order of the experiments.

The $j$-th ($1 \le j \le m$) round of cosmic rays will interfere with exactly one type of experiment equipment, determined as follows:

• A permutation $p_{j,1}, \dots, p_{j,n}$ from $1$ to $n$ is given, where $i$ appearing earlier indicates that the $i$-th experiment is more vulnerable to this round of cosmic rays. The permutations given for each round may not be the same.
• During this round of cosmic ray bombardment, the most vulnerable experiment among all unfinished and uninterfered experiments will be interfered with and subsequently cannot be conducted.

Under these conditions, Xiao I can complete a total of $(n-m)$ experiments. Xiao I hopes that the sum of their importances is as large as possible, but since Xiao I is a physicist and not an algorithm expert, Xiao I seeks your help. You need to provide a reasonable order of experiments such that the $(n-m)$ completed experiments are not interfered with by cosmic rays and the sum of their importances is maximized.

Input Format

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

The next line contains $m$ integers $a_1, a_2, \dots, a_m$, indicating how many experiments are completed before each round of cosmic rays hits the experimental base.

The following $m$ lines, each containing $n$ integers $p_1, p_2, \dots, p_n$, describe the vulnerability order of the cosmic rays for each round. 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 order of experiments you propose. You need to ensure that each experiment is conducted without being interfered with by cosmic rays and that the sum of their importances is maximized. If there are multiple solutions, output any one of them.

Sample Input and Output

Input Sample #1

3 1
1
1 2 3

Output Sample #1

1 3

Input Sample #2

3 1
1
2 3 1

Output Sample #2

2 1

Input Sample #3

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

Output Sample #3

1 4 5 2

Notes

[Sample Explanation #1]

After completing the first experiment, the cosmic rays will hit the equipment of the second experiment, so the second experiment can only be the third one. It is easy to prove that this scheme achieves the maximum importance.

[Sample Explanation #2]

In this example, if Xiao I completes the first experiment first, the cosmic rays will hit the equipment of the second experiment, resulting in the second experiment being the third one. The importance at this time is $0.625$, while the importance of the scheme given in the sample output is $0.75$.

[Sample Explanation #3]

This example has multiple valid outputs, such as 5 4 1 2 which is also a valid answer.

[Data Range]

For all test data, $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$.

[Problem Source]

From the 2023 Tsinghua University Student Programming Contest and University Invitational Tournament (THUPC2023) Finals.

Solutions and other resources can be found at https://github.com/THUSAAC/THUPC2023.

见题面 Input 部分

见题面 Output 部分