Under construction

Still being built. Things may change

Vera and Mean Sorting

Time limit2sMemory limit256 MB

Summary
Find the lexicographically smallest permutation of 1..N whose length-K window harmonic means are non-increasing, and which is not L-mean-sorted for any other window length L.
Level

Medium7 of 10

Topics
Combinatorics, Math, Greedy, Sorting
Solved
No attempts yet

Problem

The harmonic mean of a sequence of positive integers x1,x2,…,xNx_1, x_2, \dots, x_N is

H(x1,…,xN)=(∑i=1Nxi−1N)−1H(x_1, \dots, x_N) = \left( \frac{\sum_{i=1}^{N} x_i^{-1}}{N} \right)^{-1}

For an array of positive integers A=[A1,…,AN]A = [A_1, \dots, A_N] of length NN, let

M(i)=H(Ai,Ai+1,…,Ai+K−1)M(i) = H(A_i, A_{i+1}, \dots, A_{i+K-1})

Vera calls AA KK-mean-sorted if M(i)≥M(i+1)M(i) \ge M(i+1) holds for every ii with 1≤i≤N−K1 \le i \le N - K.

A permutation PP is an ordered list of NN distinct positive integers P1,P2,…,PNP_1, P_2, \dots, P_N, each of them at most NN.

Permutation PP is lexicographically smaller than permutation QQ if there is an ii (1≤i≤N1 \le i \le N) with Pi<QiP_i < Q_i such that Pj=QjP_j = Q_j for every jj with 1≤j<i1 \le j < i.

You are given the integers NN and KK. Among the permutations PP of the integers 11 through NN that are KK-mean-sorted and are not LL-mean-sorted for any LL (1≤L≤N−11 \le L \le N - 1) with L≠KL \ne K, help Vera find the lexicographically smallest one. If no such permutation exists, print 00.

Input

The input is given in the following format.

N K

Constraints:

  • 2≤N≤1002 \le N \le 100
  • 1≤K≤N−11 \le K \le N - 1
  • NN and KK are integers.

Output

Print the permutation on one line, with the numbers separated by single spaces. If no such permutation exists, print 00 on one line.

Examples2

  1. Example 1

    Input
    3 2
    
    Expected output
    2 3 1
    
  2. Example 2

    Input
    4 1
    
    Expected output
    0