Graceful Triangles

Time limit2sMemory limit1024 MB

Summary

Given n, assign distinct positive values to the n+2 vertices of a triangle strip so that edge differences cover 1 to 2n+1 exactly once, or report -1.

Level: Medium7 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Consider the following graph, made of $n$ equilateral triangles joined side by side from left to right.

The graph has $n+2$ vertices and $2n+1$ edges. The vertices are numbered from left to right as shown in the figure.

In other words, the vertices are labeled $1$ through $n+2$ , and there is an edge between every pair of vertices whose labels differ by at most $2$ .

Each vertex is assigned a positive integer. Vertex $i$ has the value $v_i$ . The value of the edge connecting vertices $i$ and $j$ is $|v_i-v_j|$ . Assign values to all vertices so that for every integer $k$ with $1 \le k \le 2n+1$ , exactly one edge has value $k$ . No vertex value may exceed $10^{18}$ .

Input

The first line contains a positive integer $n$ .

Output

If a solution exists for the given $n$ , print the values of vertices $1, 2, \ldots, n+2$ on one line, separated by spaces. Each value must be a positive integer not exceeding $10^{18}$ . Otherwise, print $-1$ .

Constraints

$1 \le n \le 200\,000$

Examples1

Example 1
Input
```
1
```
Expected output
```
3 1 4
```