31003번 - 언젠가 정렬이 될 수 있으면 좋겠네.

문제

$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ドル$인 수열은 다른 어떤 수열보다 사전 순으로 작다.

사전 순으로 최소인 수열은 다른 모든 수열보다 사전 순으로 작거나 같은 수열을 말한다.