Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

G. Painting Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given n integers, each integer is from 1 to n, all of them are pairwise distinct. You have to paint them red and blue (each integer should have exactly one color).

The cost of painting is the number of pairs (x,y) such that ymod, y is red and x is blue.

For each k \in [1, n], calculate the maximum cost of painting if exactly k integers should have a red color.

Input

The first line contains one integer n (2 \le n \le 10^5).

Output

For each k \in [1,n] print one integer — the maximum cost of painting, if exactly k integers should be red.

Examples
Input
6
Output
3 5 6 6 5 0
Input
2
Output
1 0
Input
11
Output
3 6 9 11 12 13 14 14 13 10 0


×
You are not allowed to view the requested page