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). The only line of the input contains one integer (n) ((3 \le n \le 5 \cdot 10^6)). Print (n+1) integers (p_0, p_1, \dots, p_n), where (p_k) is the number of pairs ((i, j)) with beauty (k). 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