With the launch of the “Technest” Scholarship Program in 2023 at the International Olympiad training camp, after hard trainings Fuad and Aykhan are playing a permutation puzzle game. Fuad challenges Aykhan to create a special sequence of numbers.
To win the challenge, Aykhan must generate a “composite sum permutation”, a sequence where for every i between 1 and n inclusive, the sum of the first i numbers of the permutation p of size n is always composite.
A positive integer x is considered composite if it has more than two positive integer divisors. For instance, integers like 10,25, and 222 are composite, while 1,3,31,89,97, and 13 are not.
A sequence of positive integers p=p1,p2,...,pn is defined as a permutation of length n if it contains every integer between 1 and n inclusive exactly once.
We’ll call a permutation p=p1,p2,...,pn a “composite sum permutation” if, for every index i between 1 and n inclusive, the sum of the first i elements of p, denoted as p1+p2+...+pi, is a composite number.
Help Aykhan to generate the required permutation by writing a program.
One single integer n (1≤n≤100).
If no composite sum permutation of length n exists, print a single integer −1.
Otherwise, print n integers p1,p2,...,pn such that p=p1,p2,...,pn is a “composite sum permutation”.
If there are multiple composite sum permutations of length n, you may print any of them.
In the first example for n=3, there is no answer.
In the second example for n=4, we can generate permutation “4 2 3 1”. Compute the prefix sums: “4,6,9,10”. Each of these sums is composite: 4=2⋅2,6=2⋅3,9=3⋅3,10=2⋅5".
This task consists of the following subtasks. If all tests of a subtask are passed, you will earn points for that subtask.
(25 points): n≤10;
(75 points): no additional constrains;