Pyramids

Interview

Time limit1sMemory limit1024 MB

Summary

Given N blocks, repeatedly take out the largest triangular number that fits, and print the resulting pyramid heights in decreasing order.

Level: Easy3 of 10
Topics: Greedy, Math, Implementation, Binary search
Solved: No attempts yet

Problem

Elena found a box full of cube-shaped blocks and decided to build the tallest pyramid she could, and to build more pyramids if any blocks were left over.

A pyramid must be stable and beautiful: if the bottom row of a pyramid has $k$ blocks, the row directly above it must have exactly $k-1$ blocks, and so on. A completed pyramid has exactly $k$ rows, and its top row always holds a single block. Therefore a pyramid of height $k$ uses $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ blocks.

Given the number of blocks, repeatedly build the tallest pyramid the remaining blocks allow: build the tallest possible pyramid, then from the leftover blocks build the tallest possible pyramid again, and continue until no blocks remain. Determine the heights of the pyramids that can be built.

Input

A single integer $N$ — the number of available blocks.

Output

Print the heights of the pyramids that can be built, one per line, from the tallest to the shortest.

Constraints

$1 \le N \le 1\,000\,000$

Examples2

Example 1
Input
```
20
```
Expected output
```
5
2
1
1
```
Example 2
Input
```
3
```
Expected output
```
2
```