Maximize Experiment Importance

Physicist Xiao I is testing a new conjecture and needs to conduct n different experiments. The i-th experiment (for 1 ≤ i ≤ n) has an importance of \(2^{-i}\). Each experiment is to be attempted exactly once. Xiao I can only perform one experiment at a time and, once started, cannot switch until its completion. Thus, in the absence of other constraints, the order in which experiments are performed may be represented by a permutation of \(\{1,2,\dots,n\}\>.

However, the situation is complicated by m rounds of cosmic ray attacks. In the j-th round (1 ≤ j ≤ m), after Xiao I has completed \(a_j\) experiments (note: a_j is the count of experiments finished, not the label of an experiment), a cosmic ray strikes the laboratory. It is guaranteed that \[ 1 \le a_1 < a_2 < \cdots < a_m < n-m. \] At each cosmic ray round, a permutation \(p_{j} = (p_{j,1},p_{j,2},\dots,p_{j,n})\) is provided; the experiments are ranked by vulnerability for that round (an experiment appearing earlier in \(p_{j}\) is more vulnerable). At the moment of the strike, among all experiments that are not yet completed and not already interfered, the one that is most vulnerable according to \(p_j\) (i.e. the one with the smallest index in \(p_j\)) will have its experimental apparatus disrupted – and that experiment can no longer be performed.

Thus, under these conditions, Xiao I will ultimately complete exactly \(n-m\) experiments. He wishes to choose an experiment order so that all \(n-m\) experiments that get completed are not interfered and the total importance (the sum of \(2^{-i}\) for each experiment i completed) is maximized.

Note. Since the importance of experiment \(i\) is \(2^{-i}\) (a rapidly decreasing function), it is optimal to try to have the experiments with the smallest indices executed safely. However, because of the cosmic ray rounds, some experiments (exactly \(m\) of them) will be interfered with. Your task is to choose a permutation \(\sigma\) of \(\{1,2,\dots,n\}\) (i.e. the order in which Xiao I attempts the experiments) so that after simulating the process below, the set \(S\) of experiments that are actually completed (i.e. not interfered) has size \(n-m\) and obtains the maximum possible total importance, under the following process:

• Xiao I attempts the experiments in the order \(\sigma(1), \sigma(2), \dots, \sigma(n)\).
• Whenever the number of experiments completed (i.e. attempted and not interfered) reaches some \(a_j\) (for some \(j\) from 1 to \(m\)), a cosmic ray round occurs. In that round, using the provided permutation \(p_j\) on the experiments, the experiment among those not yet attempted and not yet interfered that is most vulnerable (i.e. appears earliest in \(p_j\)) is disrupted and will never be performed.
• The process continues until all experiments have either been completed or interfered. In the end, exactly \(n-m\) experiments are completed.

Your task is to output a valid permutation \(\sigma\) so that the set of experiments that end up completed has the maximum total importance.

inputFormat

The input begins with two integers \(n\) and \(m\). The next line contains \(m\) integers: \(a_1, a_2, \dots, a_m\) (with \(1 \le a_1 < a_2 < \cdots < a_m < n-m\)). This is followed by \(m\) lines; the j-th of these lines contains a permutation of \(\{1,2,\dots,n\}\) representing \(p_{j}\) (the vulnerability order for the j-th cosmic ray round).

Note: You may assume that \(n\) is small enough (for example, \(n \le 15\)) so that a solution based on checking all subsets is acceptable.

outputFormat

Output a single line containing a permutation of \(\{1,2,\dots,n\}\) (\(n\) space‐separated integers) indicating the order in which Xiao I should attempt the experiments. This ordering must guarantee that after simulating the cosmic ray interference process described above, the \(n-m\) experiments actually performed have the maximum possible total importance.

sample

4 1
1
4 1 2 3

1 2 3 4