언젠가 정렬이 될 수 있으면 좋겠네

$N$개의 양의 정수로 이루어진 수열 $A = [A_1, \cdots, A_N]$가 주어진다. 당신은 원하는 만큼 다음 조작을 할 수 있다. 조작을 하지 않는 것도 가능하다.

• 수열에서 인접한 원소가 서로소일 때, 그 두 원소의 순서를 바꾼다.

두 수의 최대공약수가 $1$인 경우 두 수를 서로소라고 한다. 조작 이후 사전 순으로 최소인 수열 $A$를 구해보자.

첫째 줄에 수열의 길이 $N$이 주어진다. $(1 \leq N \leq 3\,000)$

둘째 줄에 $N$개의 양의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 10^9)$

조작 이후 사전 순으로 최소인 수열 $A$를 한 줄에 공백으로 구분하여 출력한다.

어떤 수열이 다른 수열보다 사전 순으로 작다는 것은 다음을 뜻한다.

• 두 수열의 첫 번째 수가 다르면, 첫 번째 수가 작은 쪽이 사전 순으로 작다.
• 두 수열의 첫 번째 수가 같다면, 첫 번째 수를 뺀 나머지를 다시 비교했을 때 사전 순으로 작은 쪽이 작다.

길이가 $0$인 수열은 다른 어떤 수열보다 사전 순으로 작다. 사전 순으로 최소인 수열은 다른 모든 수열보다 사전 순으로 작거나 같은 수열이다.