C. Caterpillar
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A caterpillar is a special type of tree.

First, it satisfies the basic property of a tree: it is a connected graph with $$$n$$$ vertices and $$$n-1$$$ edges. Then, the caterpillar can be divided into four parts: head, body, tail, and feet.

Among them, the head is vertex $$$1$$$, the body is a chain length of $$$len$$$ connected by vertices $$$2,3,\dots,len+1$$$ in order, the tail is vertex $$$len+2$$$, and the feet are other vertices directly connected to the body.

The head connects to the body, and the body connects to the tail. So vertices $$$1$$$ to $$$len+2$$$ are connected into a chain in order (There is a caterpillar with $$$n=14$$$ and $$$len=3$$$).

Now, you are given a caterpillar. You need to assign a weight to each vertex, which must be a permutation of $$$1$$$ to $$$n$$$. The edge weight is defined as the absolute difference between the weights of the two vertices it connects.

You need to construct a vertex weight scheme such that the edge weights is a permutation of $$$1$$$ to $$$n-1$$$.

Input

The first line contains two positive integers $$$n$$$ and $$$len$$$ $$$(3 \le n \le 2\cdot 10^5,1\le len\le n-2)$$$. $$$n$$$ is the total number of vertices, and $$$len$$$ is the length of the body of the caterpillar.

Vertex $$$1$$$ is the head of the caterpillar, vertices $$$2$$$ to $$$len+1$$$ are the body, and vertex $$$len+2$$$ is the tail. Vertices $$$1$$$ to $$$len+2$$$ are connected into a chain in order.

The second line contains $$$n-len-2$$$ numbers $$$a_{i+len+2}\ (2\le a_{i+len+2}\le len+1)$$$, indicating vertex number $$$i+len+2$$$ and $$$a_{i+len+2}$$$ are connected.

Output

Output one line with $$$n$$$ positive integers, which must be a permutation, so that after assigning vertex weights, the edge weights form a permutation of $$$1$$$ to $$$n-1$$$.

If there are multiple solutions, output any.

Example
Input
4 2
Output
1 4 2 3