This page is still under construction.

Parts of this page are still being built. What you see may change.

That Kind of Relationship

Time limit4.242sMemory limit1042 MB

Summary
Construct a permutation of 1..N whose number of inversions equals K, for N up to 4242.
Level

Medium5 of 10

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

Problem

Hwanju, the most sociable person in Sinsu-dong, is popular again today. The popularity is so great that Hwanju's name pours out every day in the bamboo forest.

Hwanju had a secret to that popularity: the ability to make any two people he wants into that kind of relationship!

Hwanju's method for making that kind of relationship is as follows.

  • Line up NN people in a row, from person 11 to person NN.
  • Give each person a slip of paper with one of the positive integers from 11 to NN written on it. The integers on the slips do not repeat.
  • When two different people are chosen, if the person on the left has a larger integer on their slip than the person on the right, those two people are in that kind of relationship.
  • Surprisingly, one person can be in that kind of relationship with several people.

Hwanju, the 21st century's Cupid, is worn out from too many consultations about crushes and romance. So Hwanju wants to make several that kind of relationships at once. But making too many harms public morals, and making too few leaves many singles, so he wants to make exactly KK that kind of relationships.

Hwanju saw NN friends running from far away. If he does not quickly make KK that kind of relationships, they might become Hwanju's anti-fans!

Input

Integers NN and KK are given. (2≤N≤4 2422 \leq N \leq 4\,242, 0≤K≤N(N−1)20 \leq K \leq \frac{N(N-1)}{2})

Output

Output NN integers v1,v2,⋯ ,vNv_1, v_2, \cdots, v_N separated by spaces.

viv_i is the integer on the slip that person ii received, and exactly KK that kind of relationships must be made.

A way to make exactly KK that kind of relationships always exists, and if there are several ways, output one of them.

Examples3

  1. Example 1

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

    Input
    5 7
    
    Expected output
    5 1 4 3 2
    
  3. Example 3

    Input
    3 0
    
    Expected output
    1 2 3