100 atcoder#ARC144C. [ARC144C] K Derangement

[ARC144C] K Derangement

Score : 600600 points

Problem Statement

You are given positive integers NN and KK. Find the lexicographically smallest permutation A=(A1,A2,,AN)A = (A_1, A_2, \ldots, A_N) of the integers from 11 through NN that satisfies the following condition:

  • AiiK\lvert A_i - i\rvert \geq K for all ii (1iN1\leq i\leq N).

If there is no such permutation, print -1.

What is lexicographical order on sequences?

The following is an algorithm to determine the lexicographical order between different sequences SS and TT.

Below, let SiS_i denote the ii-th element of SS. Also, if SS is lexicographically smaller than TT, we will denote that fact as S<TS \lt T; if SS is lexicographically larger than TT, we will denote that fact as S>TS \gt T.

  1. Let LL be the smaller of the lengths of SS and TT. For each i=1,2,,Li=1,2,\dots,L, we check whether SiS_i and TiT_i are the same.
  2. If there is an ii such that SiTiS_i \neq T_i, let jj be the smallest such ii. Then, we compare SjS_j and TjT_j. If SjS_j is less than TjT_j (as a number), we determine that S<TS \lt T and quit; if SjS_j is greater than TjT_j, we determine that S>TS \gt T and quit.
  3. If there is no ii such that SiTiS_i \neq T_i, we compare the lengths of SS and TT. If SS is shorter than TT, we determine that S<TS \lt T and quit; if SS is longer than TT, we determine that S>TS \gt T and quit.

Constraints

  • 2N3×1052\leq N\leq 3\times 10^5
  • 1KN11\leq K\leq N - 1

Input

Input is given from Standard Input in the following format:

NN KK

Output

Print the lexicographically smallest permutation A=(A1,A2,,AN)A = (A_1, A_2, \ldots, A_N) of the integers from 11 through NN that satisfies the condition, in the following format:

A1A_1 A2A_2 \ldots ANA_N

If there is no such permutation, print -1.

3 1
2 3 1

Two permutations satisfy the condition: (2,3,1)(2, 3, 1) and (3,1,2)(3, 1, 2). For instance, the following holds for (2,3,1)(2, 3, 1):

  • A11=1K\lvert A_1 - 1\rvert = 1 \geq K
  • A22=1K\lvert A_2 - 2\rvert = 1 \geq K
  • A33=2K\lvert A_3 - 3\rvert = 2 \geq K
8 3
4 5 6 7 8 1 2 3
8 6
-1