Problems
Fuad’s challenge
Fuad’s challenge
\includegraphics{https://eolympusercontent.com/images/67etuei7ft6sjbf02jlcibphbc.gif}
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 “\textbf{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 \textbf{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 = p_1, p_2, ..., p_n$ is defined as a \textbf{permutation} of length $n$ if it contains every integer between $1$ and $n$ inclusive exactly once.
We’ll call a permutation $p = p_1, p_2, ..., p_n$ a “\textbf{composite sum permutation}” if, for every index $i$ between $1$ and $n$ inclusive, the sum of the first $i$ elements of $p$, denoted as $p_1 + p_2 + ... + p_i$, is a composite number.
Help Aykhan to generate the required permutation by writing a program.
\InputFile
One single integer $n~(1 \le n \le 100)$.
\OutputFile
If no composite sum permutation of length $n$ exists, print a single integer $-1$.
Otherwise, print $n$ integers $p_1, p_2, ..., p_n$ such that $p = p_1, p_2, ..., p_n$ is a “\textbf{composite sum permutation}”.
If there are multiple composite sum permutations of length $n$, you may print any of them.
\Examples
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 \cdot 2, 6 = 2 \cdot 3, 9 = 3 \cdot 3, 10 = 2 \cdot 5$".
\Scoring
This task consists of the following subtasks. If all tests of a subtask are passed, you will
earn points for that subtask.
\begin{enumerate}
\item ($25$ points): $n \le 10$;
\item ($75$ points): $no~additional~constrains$;
\end{enumerate}
Input example #1
3
Output example #1
-1
Input example #2
4
Output example #2
4 2 3 1