시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 26 11 9 60.000%

문제

길이가 N인 수열 A = {a1 ~ an}이 있을 때, A의 GCD 테이블 G는 아래 공식에 의해 정의된다.

gij = gcd(ai, aj)

gcd(x, y)란 두 수 x, y의 최대 공약수를 뜻한다. 예를 들어 길이가 4인 수열 A = {4, 3, 6, 2}의 GCD 테이블은 아래와 같다.

GCD 테이블 G를 구성하는 모든 gij가 주어질 때, 원본 수열 a를 구하여라.

입력

첫 줄에 수열 A의 길이 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 A의 GCD 테이블의 N*N개의 값이 임의의 순서로 공백을 사이에 두고 주어진다. 모든 GCD 테이블의 숫자는 양의 정수이며, 1,000,000,000을 넘지 않는다. 원본 수열 A를 구할 수 없는 경우는 주어지지 않는다.

출력

한 줄에 공백으로 구분된 N개의 양의 정수를 출력한다. 만약 가능한 답이 여러개라면, 그 중 아무거나 출력한다.

예제 입력 1

4
2 1 2 3 4 3 2 6 1 1 2 2 1 2 3 2

예제 출력 1

4 3 6 2

예제 입력 2

1
42

예제 출력 2

42

예제 입력 3

2
1 1 1 1

예제 출력 3

1 1

힌트