С запуском программы стипендий "Technest" в 2023 году на международном тренировочном лагере олимпиады, после усердных тренировок Фуад и Айхан играют в игру с перестановкой чисел. Фуад бросает вызов Айхану, создав особую последовательность чисел.
Чтобы выиграть вызов, Айхан должен сгенерировать "перестановку с составной суммой" — последовательность, где для каждого i от 1 до n включительно сумма первых i чисел перестановки p размером n всегда является составным числом.
Положительное целое число x считается составным, если у него больше двух положительных целых делителей. Например, целые числа такие как 10,25 и 222 являются составными, в то время как 1,3,31,89,97 и 13 — нет.
Последовательность положительных целых чисел p=p1,p2,...,pn определяется как перестановка длины n, если она содержит каждое целое число от 1 до n включительно ровно один раз.
Мы назовем перестановку p=p1,p2,...,pn "перестановкой с составной суммой", если для каждого индекса i от 1 до n включительно сумма первых i элементов p, обозначенная как p1+p2+...+pi, является составным числом.
Помогите Айхану сгенерировать необходимую перестановку, написав программу.
Одно целое число n (1≤n≤100).
Если не существует перестановки с составной суммой длины n, выведите одно целое число −1.
В противном случае выведите n целых чисел p1,p2,...,pn, таких что p=p1,p2,...,pn является "перестановкой с составной суммой".
Если существует несколько перестановок с составной суммой длины n, Вы можете вывести любую из них.
В первом примере для n=3 нет ответа.
Во втором примере для n=4 мы можем сгенерировать перестановку "4 2 3 1". Вычислим префиксные суммы: "4,6,9,10". Каждая из этих сумм является составным числом: 4=2⋅2,6=2⋅3,9=3⋅3,10=2⋅5".
Эта задача состоит из следующих подзадач. Если все тесты подзадачи пройдены успешно, Вы заработаете баллы за эту подзадачу.
(25 баллов): n≤10;
(75 баллов): без дополнительных ограничений;