Hide

# Problem DMissing Gnomes

A family of $n$ gnomes likes to line up for a group picture. Each gnome can be uniquely identified by a number $1..n$ written on their hat.

Suppose there are $5$ gnomes. The gnomes could line up like so: $1, 3, 4, 2, 5$.

Now, an evil magician will remove some of the gnomes from the lineup and wipe your memory of the order of the gnomes. The result is a subsequence, perhaps like so: $1, 4, 2$.

He then tells you that if you ordered all permutations of $1..n$ in lexicographical order, the original sequence of gnomes is the first such permutation which contains the remaining subsequence. Your task is to find the original sequence of gnomes.

## Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers $n$ and then $m$ ($1 \le m \le n \le 10^5$), where $n$ is the number of gnomes originally, and $m$ is the number of gnomes remaining after the evil magician pulls his trick. Each of the next $m$ lines will contain a single integer $g$ ($1 \le g \le n$). These are the remaining gnomes, in order. The values of $g$ are guaranteed to be unique.

## Output

Output $n$ lines, each containing a single integer, representing the first permutation of gnomes that could contain the remaining gnomes in order.

Sample Input 1 Sample Output 1
5 3
1
4
2

1
3
4
2
5

Sample Input 2 Sample Output 2
7 4
6
4
2
1

3
5
6
4
2
1
7

CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show