One-sequence

Time limit1sMemory limit128 MB

Summary

Find the lexicographically smallest walk of length n starting at 0 with +/-1 steps whose total sum is S, or report that none exists.

Level: Medium6 of 10
Topics: Greedy, Implementation, Math, Prefix sum
Solved: No attempts yet

Problem

We call a sequence of integers a one-sequence when the difference between any two consecutive elements is either $1$ or $-1$ and its first element is $0$ . Formally, $[a_1, a_2, \ldots, a_n]$ is a one-sequence when:

for every $k$ with $1 \le k < n$ : $|a_k - a_{k+1}| = 1$ , and
$a_1 = 0$ .

You are given the length $n$ of the sequence and the required sum $S$ of its elements. Several one-sequences of length $n$ can share the same sum, so you must output the lexicographically smallest one: compare two sequences element by element and prefer the one whose first differing element is smaller (because $a_1$ is always $0$ , the order is decided from $a_2$ onward). If no one-sequence of length $n$ sums to $S$ , report that no such sequence exists.

Input

The first line contains an integer $n$ with $1 \le n \le 10000$ , the number of elements in the sequence. The second line contains an integer $S$ with $|S| \le 50000000$ , the required sum of the elements.

Output

If a one-sequence of length $n$ whose elements sum to $S$ exists, print its elements one per line, giving the lexicographically smallest such sequence (the $k$ -th element on the $k$ -th line). Otherwise print NIE (Polish for "no").

Examples4

Example 1
Input
```
8
4
```
Expected output
```
0
-1
0
-1
0
1
2
3
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
1
5
```
Expected output
```
NIE
```
Example 4
Input
```
2
1
```
Expected output
```
0
1
```