Problem I

Mirko dreamt of a histogram last night that consists of $N$ columns. Each column is one meter wide and the heights of the columns in meters are $h_1, h_2, \ldots , h_ N$.

The capacity of a histogram is the maximal amount of water that a histogram can hold so that the configuration of the water is “stable”, or, in other words, that it doesn’t move under the influence of gravity. Figure 1 depicts an example of a stable configuration.

Figure 1: Stable configuration of a histogram

Formally, let us denote the heights of water above the columns with $v_1, v_2, \ldots , v_ N$. The configuration of the water is stable if the following holds:

  • $h_ i + v_ i \leq h_{i-1} + v_{i-1}$, for each $i > 2$ such that $v_ i > 0$

  • $h_ i + v_ i \leq h_{i+1} + v_{i+1}$, for each $i \leq N - 1$ such that $v_ i > 0$

  • $v_1 = 0$ and $v_ N = 0$

When Mirko woke up, he wanted to know whether he could somehow choose the heights of columns that are a permutation of the set $\{ 1, 2, \ldots , N \} $ such that the capacity of such histogram is equal to its lucky number $X$? Help Mirko and find one histogram that meets his requirements.


The first line of input contains integers $N$ and $X$ ($1 \leq N \leq 1\, 000\, 000$, $1 \leq X \leq 10^{15}$).


If a histogram of capacity exactly $X$ does not exist, output -1. Otherwise, output numbers $h_1, h_2, \ldots , h_ N$ that meet the given requirements in the first line separated by space. If there are multiple such solutions, output any.

Sample Input 1 Sample Output 1
3 1
3 1 2
Sample Input 2 Sample Output 2
4 1
4 3 1 2
Sample Input 3 Sample Output 3
8 17
6 2 3 1 8 4 5 7

Please log in to submit a solution to this problem

Log in