```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)

	total := n * n
	nums := make([]int, total)
	for i := 0; i < total; i++ {
		fmt.Fscan(reader, &nums[i])
	}

	// Sort in decreasing order
	sort.Sort(sort.Reverse(sort.IntSlice(nums)))

	// Use a map to track available counts
	countMap := make(map[int]int)
	for _, v := range nums {
		countMap[v]++
	}

	result := make([]int, 0, n)

	// gcdCount[i][j] will store gcd(result[i], result[j]) for already found elements
	// We need to track how many times each gcd appears among pairs of result elements

	for idx := 0; idx < total; idx++ {
		v := nums[idx]
		if countMap[v] <= 0 {
			continue
		}

		// Try to add v to result
		// v would be gcd(v, v) = v, so we need to remove one occurrence of v for the diagonal
		// and for each existing element in result, remove two occurrences of gcd(v, existing)

		// First check if we can do it (the problem guarantees a solution, so we just proceed)
		countMap[v]--

		// For each already picked element, compute gcd and remove 2 occurrences
		ok := true
		removed := make([]int, 0, len(result))
		for _, r := range result {
			g := gcd(v, r)
			if countMap[g] < 2 {
				ok = false
				break
			}
			countMap[g] -= 2
			removed = append(removed, g)
		}

		if ok {
			result = append(result, v)
			if len(result) == n {
				break
			}
		} else {
			// Restore
			for _, g := range removed {
				countMap[g] += 2
			}
			countMap[v]++
			// Mark this specific occurrence as used/skipped - but we need to skip it
			// Actually since countMap[v] was restored, we just continue
			// But we need to not pick this value again for this iteration
			// The problem guarantees a valid solution exists, so this path means
			// v isn't actually an element of a. We just skip.
			// We don't re-add to consider; the count is restored so next occurrence of same value can try
		}
	}

	for i, v := range result {
		if i > 0 {
			fmt.Fprint(writer, " ")
		}
		fmt.Fprint(writer, v)
	}
	fmt.Fprintln(writer)
}
```