C. Произведение 1 по модулю N
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

А вот первые слова маленького Эхаба: «Дано целое число $$$n$$$, найдите самую длинную подпоследовательность массива $$$[1,2, \ldots, n-1]$$$, произведение элементов которой равно $$$1$$$ по модулю $$$n$$$». Решите эту задачу.

Последовательность $$$b$$$ является подпоследовательностью массива $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, всех) элементов. Произведение элементов пустой подпоследовательности равно $$$1$$$.

Входные данные

В единственной строке дано целое число $$$n$$$ ($$$2 \le n \le 10^5$$$).

Выходные данные

В первой строке выведите длину найденной подпоследовательности.

Во второй строке выведите элементы подпоследовательности в возрастающем порядке.

Если существует несколько ответов, выведите любой.

Примеры
Входные данные
5
Выходные данные
3
1 2 3
Входные данные
8
Выходные данные
4
1 3 5 7
Примечание

В первом примере произведение элементов равно $$$6$$$, что равно $$$1$$$ по модулю $$$5$$$. Единственная более длинная последовательность это $$$[1,2,3,4]$$$. Произведение ее элементов равно $$$24$$$, что равно $$$4$$$ по модулю $$$5$$$. Поэтому, ответ это $$$[1,2,3]$$$.