J. Jiggly Sequence
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an integer $$$k \geq 1$$$. A sequence of $$$n$$$ numbers $$$s_1, s_2, \ldots, s_n$$$ is called jiggly if, for any indices $$$i, j$$$ such that $$$1 \leq |i - j| \leq k$$$, the condition $$$s_i \neq s_j$$$ is satisfied.

You are also given an array $$$A$$$ of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$. Find any way to permute the elements of $$$A$$$ so that it becomes jiggly. Also, for every position $$$i$$$, find how many different values appear in the $$$i$$$-th position across all possible jiggly permutations of $$$A$$$.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 3 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$): the elements of the initial array $$$A$$$.

Output

If it is impossible to permute the array for it to become jiggly, print a single integer $$$-1$$$.

Otherwise, print two lines. The first line should contain $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq n$$$): the elements of any valid jiggly permutation of the initial array.

The second line should contain $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq n$$$), meaning that if we consider all possible jiggly permutations of the array $$$A$$$, there are exactly $$$c_i$$$ different values in position $$$i$$$ in them.

Examples
Input
7 2
3 2 1 1 1 2 3
Output
1 2 3 1 2 3 1 
1 2 2 1 2 2 1 
Input
4 1
4 4 4 2
Output
-1
Note

In the first example, the only valid permutations are $$$(1, 2, 3, 1, 2, 3, 1)$$$ and $$$(1, 3, 2, 1, 3, 2, 1)$$$.

In the second example, it is impossible to permute the array in such a way that no two $$$4$$$-s stand next to each other.