F. Binary Search with One Swap
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$:

  1. initialize $$$l = 1$$$ and $$$r = n$$$;
  2. if $$$l \gt r$$$, terminate the algorithm and report that the desired element was not found;
  3. compute $$$m = \lfloor \frac{l + r}{2} \rfloor$$$;
  4. if $$$a_m = x$$$, terminate the algorithm and report that the desired element was found;
  5. if $$$a_m \lt x$$$, set $$$l = m + 1$$$, otherwise set $$$r = m - 1$$$;
  6. 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$$$.

Examples
Input
4
Output
0 0 3 3 0
Input
5
Output
0 0 2 4 4 0
Input
3
Output
0 1 2 0
Input
13
Output
0 0 0 0 0 0 1 3 8 9 21 24 12 0
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.