Перетасуй#515

Перетасуй

Дано масив цілих невід'ємних чисел довжини .

Позначимо операцію обміну наступним чином:

Для будь-якого масиву довжини , позначимо його ціну за максимальне значення c_i + c_j по всіх , для яких виконується 1 \leq i < j \leq n та gcd(i, j) > 1, або за , якщо таких не існує.

Знайдіть масив довжини такий, що можна отримати за допомогою будь-якої кількості операцій обміну, та ціна масиву мінімальна.

Input

Перший рядок містить одне ціле число (1 \leq n \leq 10^6) — довжина масиву .

Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (0 \leq a_i \leq \textbf{3}) — елементи масиву .

Output

У єдиному рядку виведіть цілих чисел — елементи масиву . Якщо правильних відповідей декілька, дозволяється вивести будь-яку з них.

Examples

Example 1

Loading
Loading

Scoring

  1. ( балів): n \leq 10;

  2. ( балів): n \leq 50; відповідь можна отримати, зробивши не більше однієї операції обміну;

  3. ( балів): n \leq 1\,000; відповідь можна отримати, зробивши не більше однієї операції обміну;

  4. ( балів): відповідь можна отримати, зробивши не більше однієї операції обміну;

  5. ( балів): \max(a_i) \leq 1; n \leq 1\,000; часткове оцінювання;

  6. ( балів): \max(a_i) \leq 1;

  7. ( балів): \max(a_i) \leq 2; n \leq 1\,000; часткове оцінювання;

  8. ( балів): \max(a_i) \leq 2;

  9. ( балів): n \leq 1\,000; часткове оцінювання;

  10. ( балів): без додаткових обмежень.

У блоках, де є часткове оцінювання, ваше рішення отримає половину балів, якщо в усіх тестах цього блоку ваше рішення виводить масив, у якому ціна або збігається з правильним рішенням, або на більше.