Rigged Lottery

Time limit2sMemory limit1024 MB

Summary

Given k, c, and a ticket of length k, find the shortest sequence over 1 to c that contains every length-k sequence as a subsequence except that ticket.

Level: Hard8 of 10
Topics: String, Combinatorics, Greedy
Solved: No attempts yet

Problem

The ICPC Genie gave you the power to manipulate a single event. You remember that you bought a lottery ticket yesterday, so you decide to use the power to manipulate the lottery results.

Every lottery ticket is a unique sequence of $k$ numbers, and no two tickets have the same sequence. Each number is between $1$ and $c$ , and the same number can appear more than once in a ticket. For example, when $k = 3$ and $c = 2$ , the possible tickets are $(1,1,1)$ , $(1,1,2)$ , $(1,2,1)$ , $(1,2,2)$ , $(2,1,1)$ , $(2,1,2)$ , $(2,2,1)$ , and $(2,2,2)$ .

A lottery machine first picks a finite sequence of numbers, where each number is between $1$ and $c$ and can occur more than once. This sequence is called the losing sequence. If the losing sequence has a ticket as a subsequence, that ticket is a losing ticket. Otherwise, the ticket is a winning ticket. A losing sequence can have several winning tickets, in which case the prize is split evenly among them.

For example, if the losing sequence is $(2,1,2,2,1)$ , the ticket $(1,1,1)$ is a winning ticket, but the ticket $(2,2,2)$ is a losing ticket.

You want to build a losing sequence in which your ticket is the only winning ticket. More winning tickets mean a smaller share of the prize. So the losing sequence must contain every sequence of length $k$ as a subsequence, except your own ticket.

Given $k$ , $c$ , and your ticket, find the shortest losing sequence in which your ticket is the only winning ticket. If several shortest sequences exist, output the lexicographically first one.

Input

The first line contains a positive integer $k$ , the length of a lottery ticket. The second line contains a positive integer $c$ ( $2 \le k + c \le 10\,000$ ), the largest number on a ticket. The third line contains $k$ integers, separated by whitespace, that form your ticket. Each integer is between $1$ and $c$ .

Output

Print exactly one line containing the shortest sequence in which every sequence of length $k$ except your ticket is a subsequence. Separate the numbers with a whitespace. If several such sequences exist, print the lexicographically first one.

Examples3

Example 1
Input
```
1
4
3
```
Expected output
```
1 2 4
```
Example 2
Input
```
2
3
3 3
```
Expected output
```
1 2 3 1 2
```
Example 3
Input
```
3
2
1 2 1
```
Expected output
```
2 2 1 1 1 2 2
```