Дано масив цілих невід'ємних чисел довжини .
Позначимо операцію обміну наступним чином:
Обрати індекси такі, що 1 \leq i < j \leq n.
Поміняти місцями елементи a_i та a_j.
Для будь-якого масиву довжини , позначимо його ціну за максимальне значення c_i + c_j по всіх , для яких виконується 1 \leq i < j \leq n та gcd(i, j) > 1, або за , якщо таких не існує.
Знайдіть масив довжини такий, що можна отримати за допомогою будь-якої кількості операцій обміну, та ціна масиву мінімальна.
Перший рядок містить одне ціле число (1 \leq n \leq 10^6) — довжина масиву .
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (0 \leq a_i \leq \textbf{3}) — елементи масиву .
У єдиному рядку виведіть цілих чисел — елементи масиву . Якщо правильних відповідей декілька, дозволяється вивести будь-яку з них.
Example 1
( балів): n \leq 10;
( балів): n \leq 50; відповідь можна отримати, зробивши не більше однієї операції обміну;
( балів): n \leq 1\,000; відповідь можна отримати, зробивши не більше однієї операції обміну;
( балів): відповідь можна отримати, зробивши не більше однієї операції обміну;
( балів): \max(a_i) \leq 1; n \leq 1\,000; часткове оцінювання;
( балів): \max(a_i) \leq 1;
( балів): \max(a_i) \leq 2; n \leq 1\,000; часткове оцінювання;
( балів): \max(a_i) \leq 2;
( балів): n \leq 1\,000; часткове оцінювання;
( балів): без додаткових обмежень.
У блоках, де є часткове оцінювання, ваше рішення отримає половину балів, якщо в усіх тестах цього блоку ваше рішення виводить масив, у якому ціна або збігається з правильним рішенням, або на більше.