Print the permutation of array A such that gcd of prefix array created is lexi. greatest

we are given an array A and we have to choose the permutation of A such that a new array B created from the gcd of prefix elements, is lexicographically greatest.
N <= 10^5
A[i] <= 10^8
time complexity needed = nlogn.
Example :
A= [ 7, 8, 4, 2, 16, 9]
output : A = [ 16, 8 , 4, 2, 9, 7]
B = [ gcd(16), gcd(16, 8), gcd(16,8,4), gcd(16,8,4,2) , gcd(16,8,4,2,9), gcd(16,8,4,2, 9,7) ]
B = [ 16, 8, 4, 2, 1, 1]