Mr. A's Magic Balls

Mr. A discovered a sequence of $n$ magical balls in his closet. Each ball is a unique color, conveniently numbered from $1$ to $n$. Importantly, $n$ is an even number.

Mr. A also has an empty array $Q$, where he plans to record the colors of these balls.

He will perform $\frac{n}{2}$ operations, each involving the following steps: Mr. A selects a pair of adjacent balls from the sequence, removes them, and appends their colors to the beginning of array $Q$. The order of the colors in $Q$ will match their order in the original sequence. After removing a pair, the sequence is rejoined, forming a new sequence.

For instance, if the sequence of ball colors is $\{1,5,3,2,6,4\}$, Mr. A could first add the pair $\{2,6\}$ to the start of $Q$, then $\{3,4\}$, and finally $\{1,5\}$. This results in the array $Q=[1,5,3,4,2,6]$.

Mr. A wants to know the lexicographically smallest array $Q$ possible after performing all operations. Lexicographical order is determined by comparing arrays element by element from the start: the first differing element decides which array is smaller. For example, $[10,3,1]<[10,4,5]$, $[1,1,1]<[1,2,3]$, and $[1,2,3]<[10,10,10]$.

Your task is to help Mr. A find the first $k$ elements of the smallest possible array $Q$.

Input

The first line contains two integers $n$ and $k$ $(1\le k\le n\le 10^6)$. It is guaranteed that $n$ is even.

The second line contains $n$ distinct integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$, representing the colors of the balls in the sequence.

Output

Output $k$ integers $q_1,q_2,\dots ,q_k$—the first elements of the smallest possible array $Q$.

Examples

Scoring

1. ($8$ points): $n\le 10^5,k=1$;

2. ($5$ points): $n\le 10^5,k=2$;

3. ($19$ points): $n\le 14$;

4. ($16$ points): $n\le 10^3$;

5. ($10$ points): $n\le 10^5,k\le 20$;

6. ($24$ points): $n\le 10^5$;

7. ($18$ points): without additional constraints.