Consider the following algorithm for searching for an integer $$$x$$$ in an array $$$a$$$ of length $$$n$$$, where the elements are numbered from $$$1$$$ to $$$n$$$:

initialize $$$l = 1$$$ and $$$r = n$$$;
if $$$l \gt r$$$, terminate the algorithm and report that the desired element was not found;
compute $$$m = \lfloor \frac{l + r}{2} \rfloor$$$;
if $$$a_m = x$$$, terminate the algorithm and report that the desired element was found;
if $$$a_m \lt x$$$, set $$$l = m + 1$$$, otherwise set $$$r = m - 1$$$;
go to step $$$2$$$.

It can be shown that if the array $$$a$$$ is sorted in non-decreasing order, then any element of $$$a$$$ will be successfully found by this algorithm.

Your task is as follows: for a given number $$$n$$$, consider all pairs $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$. For each of these pairs, you need to calculate its beauty — the number of integers $$$x$$$ from $$$1$$$ to $$$n$$$ that can be successfully found by the described algorithm if we take the array $$$a = [1, 2, 3, \dots, n]$$$ and swap the elements $$$a_i$$$ and $$$a_j$$$. After that, for each $$$k$$$ from $$$0$$$ to $$$n$$$, you need to output $$$p_k$$$ — the number of pairs with beauty $$$k$$$.

Input

The only line of the input contains one integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^6$$$).

Output

Print $$$n+1$$$ integers $$$p_0, p_1, \dots, p_n$$$, where $$$p_k$$$ is the number of pairs $$$(i, j)$$$ with beauty $$$k$$$.

Note

Consider an example where $$$n = 4$$$:

if we swap $$$a_1$$$ and $$$a_2$$$, then $$$1$$$, $$$3$$$, and $$$4$$$ can be successfully found;
if we swap $$$a_1$$$ and $$$a_3$$$, then $$$2$$$ and $$$4$$$ can be successfully found;
if we swap $$$a_2$$$ and $$$a_3$$$, then $$$1$$$, $$$3$$$, and $$$4$$$ can be successfully found;
if we swap $$$a_1$$$ and $$$a_4$$$, then $$$2$$$ and $$$3$$$ can be successfully found;
if we swap $$$a_2$$$ and $$$a_4$$$, then $$$1$$$ and $$$4$$$ can be successfully found;
if we swap $$$a_3$$$ and $$$a_4$$$, then $$$1$$$, $$$2$$$, and $$$4$$$ can be successfully found.

Binary Search with One Swap

Examples