D. Graceful Triangles
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Consider the following graph in the shape of $$$n$$$ equilateral triangles stitched together horizontally:

This graph has $$$n+2$$$ vertices and $$$2n+1$$$ edges. The vertices are labeled in the order of increasing horizontal position, as in the image above.

In other words, the graph has $$$n+2$$$ vertices labeled from $$$1$$$ through $$$n+2$$$, and $$$2n+1$$$ edges connecting all pairs of vertices whose labels differ by at most $$$2$$$.

A positive integer value is assigned to each vertex. Vertex $$$i$$$ has the value of $$$v_i$$$. The value of an edge that connects vertices $$$i$$$ and $$$j$$$ is $$$|v_i - v_j|$$$. Find a way to assign values to all vertices so that for every positive integer $$$k$$$ up to $$$2n+1$$$ inclusive, exactly one edge has the value of $$$k$$$. The value of any vertex cannot exceed $$$10^{18}$$$.

Input

The first line contains $$$n$$$, a positive integer.

Output

If a solution exists for the given $$$n$$$, print the values assigned to the vertices $$$1, 2, \ldots, n+2$$$ in one line, separated by spaces. The values must be positive integers not exceeding $$$10^{18}$$$. Otherwise, print $$$-1$$$.

Scoring
  • $$$1 \le n \le 200\,000$$$
Example
Input
1
Output
3 1 4