Shuffle#12345
Given an array of non-negative integers of length .
Define the swap operation as follows:
Select indices such that 1 \leq i < j \leq n.
Swap elements a_i and a_j.
For any array of length , define its cost by the maximum value of c_i + c_j for all such that 1 \leq i < j \leq n and gcd(i, j) > 1, or if no such exist.
Find an array of length such that can be obtained by any number of swap operations, and the cost of the array is minimal.
The first line contains a single integer (1 \leq n \leq 10^6) — the length of the array .
The second line contains integers a_1, a_2, \ldots, a_n (0 \leq a_i \leq \textbf{3}) — the elements of array .
Output a single line with integers — the elements of array . If there are multiple correct answers, any one of them is allowed.
Example 1
( points): n \leq 10;
( points): n \leq 50; the answer can be obtained with at most one swap operation;
( points): n \leq 1\,000; the answer can be obtained with at most one swap operation;
( points): the answer can be obtained with at most one swap operation;
( points): \max(a_i) \leq 1; n \leq 1\,000;
( points): \max(a_i) \leq 1;
( points): \max(a_i) \leq 2; n \leq 1\,000;
( points): \max(a_i) \leq 2;
( points): n \leq 1\,000;
( points): without additional constraints.
In blocks with partial grading, your solution will receive half points if for all tests in that block your solution outputs an array where the cost either matches the correct solution or is more.