Not Fun Problem

Time limit2sMemory limit1024 MB

Summary

Given N and M, build a length-N integer array with values in [0, 10^9] whose contiguous subarray sums cover every value from 0 to M and no value above M.

Level: Medium6 of 10
Topics: Array, Math
Solved: No attempts yet

Problem

This problem is not fun. Most people would skip a problem like this, but you, a contestant, have to solve it.

Given $N$ and $M$ , find a sequence $A$ of length $N$ that satisfies all of the following conditions. Such a sequence always exists.

For every integer $x$ with $0 \leq x \leq M$ , there exist integers $l$ and $r$ such that $\sum_{k=l}^{r} A_k = x$ . ( $1 \leq l \leq r \leq N$ )
For every integer $x$ with $x > M$ , there do not exist integers $l$ and $r$ such that $\sum_{k=l}^{r} A_k = x$ . ( $1 \leq l \leq r \leq N$ )
For every integer $i$ with $1 \leq i \leq N$ , $0 \leq A_i \leq 10^9$ .
Every element of sequence $A$ is an integer.

Input

The first line contains two integers $N$ and $M$ , separated by a space. ( $1 \leq N \leq 1\,000$ ; $0 \leq M \leq \left\lfloor N^2/4 \right\rfloor$ )

Output

Print $A_1, A_2, \cdots, A_N$ on the first line, separated by spaces.

Examples3

Example 1
Input
```
4 3
```
Expected output
```
0 0 1 2
```
Example 2
Input
```
5 5
```
Expected output
```
0 2 0 2 1
```
Example 3
Input
```
4 4
```
Expected output
```
0 2 1 1
```