## DMOPC '21 Contest 5 P1 - Permutations & Primes

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

At the Phoenix Wonderland carnival, you found a mysterious booth that proposes an interesting challenge. The operator (some strange floating nuigurumi) will give you an integer , and you are to find any permutation of wherein every adjacent sum in the permutation is non-prime. That is, for all , we must have be non-prime. Can you find any such permutation, or determine that none exists?

#### Input Specification

The first and only line of input contains a single integer .

#### Output Specification

If there exists no valid permutation, output on a line by itself.

Otherwise, output space-separated integers on a single line, representing a permutation of wherein every adjacent sum in the permutation is non-prime.

#### Sample Input 1

7

#### Sample Output 1

7 2 4 6 3 5 1

#### Explanation for Sample 1

Note that the adjacent pairs have sums of , none of which are prime.

#### Sample Input 2

2

#### Sample Output 2

-1

#### Explanation for Sample 2

Note that which is prime, so regardless of order the sum of the one pair is prime.