Orange Island Trip

Time limit1sMemory limit1024 MB

Summary

Given N, find a walk along trees whose numbers are coprime at each step, eating the oranges on every tree (phi(k) on tree k), or report -1.

Level: Medium6 of 10
Topics: Number theory, Graph, Implementation
Solved: No attempts yet

Problem

Bru set off on a trip to Orange Island. The island has $N$ orange trees, numbered from 1 to $N$ .

Bru asked the orange tree No. 1 on the island about the island's history. Tree No. 1 recited the history as follows.

"In the beginning, each of the $N$ orange trees had no oranges at all.

One day, every tree shook hands with every other tree exactly once. When the numbers of the two trees in a handshake are coprime, the two trees form a good relationship, and the tree with the larger number grows one orange.

After all the handshakes were done, tree No. 1, which had no orange yet, grew one orange."

- Orange tree No. 1

For example, when $N=4$ , trees 1 and 2 each have one orange, and trees 3 and 4 each have two oranges.

Bru wants to eat every orange on the island. Specifically, Bru eats oranges by following this process.

Move to any tree and eat exactly one orange there.
Then move to a tree that has a good relationship with the current tree and eat exactly one orange there.
Repeat step 2 until all oranges are eaten.

Input

The first line contains the number of orange trees $N$ on the island.

Output

If Bru can eat all the oranges, print the numbers of the orange trees in the order Bru eats the oranges, in the same format as the sample output. Otherwise, print -1.

Constraints

$1 \le N \le 10^3$

Examples1

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