Kuroni and the Score Distribution
Contest: Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)
Difficulty rating: 2200
Tags: constructive algorithms, greedy, implementation, math

Kuroni is the coordinator of the next Mathforces round written by the "Proof by AC" team. All the preparation has been done, and he is discussing with the team about the score distribution for the round.

The round consists of $$$n$$$ problems, numbered from $$$1$$$ to $$$n$$$. The problems are ordered in increasing order of difficulty, no two problems have the same difficulty. A score distribution for the round can be denoted by an array $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is the score of $$$i$$$-th problem.

Kuroni thinks that the score distribution should satisfy the following requirements:

- The score of each problem should be a positive integer not exceeding $$$10^9$$$.
- A harder problem should grant a strictly higher score than an easier problem. In other words, $$$1 \leq a_1 < a_2 < \dots < a_n \leq 10^9$$$.
- The balance of the score distribution, defined as the number of triples $$$(i, j, k)$$$ such that $$$1 \leq i < j < k \leq n$$$ and $$$a_i + a_j = a_k$$$, should be exactly $$$m$$$.

Help the team find a score distribution that satisfies Kuroni's requirement. In case such a score distribution does not exist, output $$$-1$$$.

Input format:
The first and single line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5000$$$, $$$0 \leq m \leq 10^9$$$) — the number of problems and the required balance.

Output format:
If there is no solution, print a single integer $$$-1$$$.

Otherwise, print a line containing $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, representing a score distribution that satisfies all the requirements. If there are multiple answers, print any of them.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$3$$$ triples $$$(i, j, k)$$$ that contribute to the balance of the score distribution.

- $$$(1, 2, 3)$$$
- $$$(1, 3, 4)$$$
- $$$(2, 4, 5)$$$

Example input:
5 3

Example output:
4 5 9 13 18

Example input:
8 0

Example output:
10 11 12 13 14 15 16 17

Editorial:
Firstly, note that for each $$$i$$$, there can't be more than $$$\lfloor \frac{i-1}{2} \rfloor$$$ triples of form $$$(x, y, i)$$$ with $$$a_x + a_y = a_i$$$. This is true as every index $$$j$$$ can meet at most once among all $$$x, y$$$ (as the third index is uniquely determined by $$$i$$$, $$$j$$$). Therefore, the answer can't exceed $$$\lfloor \frac{0}{2} \rfloor + \lfloor \frac{1}{2} \rfloor + \dots + \lfloor \frac{n-1}{2} \rfloor = N$$$. So, if $$$m>N$$$, answer is $$$-1$$$.
Note that the sequence $$$a_i = i$$$ has balance exactly $$$N$$$. Now we show how to construct the answer for any given $$$m\le N$$$. If $$$m = N$$$, we just output sequence $$$a_i = i$$$.
Now suppose that $$$\sum_{i = 1}^k \lfloor \frac{i-1}{2} \rfloor \le m < \sum_{i = 1}^{k+1} \lfloor \frac{i-1}{2} \rfloor$$$ for some $$$k$$$. Then let's choose $$$a_i = i$$$ for $$$i = 1, 2, \dots, k$$$, and choose $$$a_{k+1} = 2k + 1 - 2(m - \sum_{i = 1}^k \lfloor \frac{i-1}{2})$$$. We get balance of $$$\sum_{i = 1}^k \lfloor \frac{i-1}{2} \rfloor$$$ from first $$$k$$$ numbers, and $$$m - \sum_{i = 1}^k \lfloor \frac{i-1}{2} \rfloor$$$ triples of form $$$(x, y, k+1)$$$ (precisely $$$(k + 1 - 2(m - \sum_{i = 1}^k \lfloor \frac{i-1}{2} \rfloor), k, k+1), (k + 2 - 2(m - \sum_{i = 1}^k \lfloor \frac{i-1}{2} \rfloor), k-1, k+1), \dots$$$).
We have achieved the desired balance now, and just have to choose $$$a_i$$$ for $$$i>k+1$$$ such that they don't form any other good triples. For this, we can take $$$a_i = 10^8 + 1 + 10^4i$$$ for $$$i>k+1$$$, for example (sum of two odd numbers can't be odd, no $$$a_i$$$ with $$$i>k+1$$$ can be equal to $$$a_x + a_y$$$ with $$$x, y\le k+1$$$ as $$$a_i$$$ is much larger, and $$$a_x + a_y = a_i$$$ for $$$i, y>k+1, x\le k+1$$$ is impossible as $$$a_x<10^4$$$).