```go
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"strconv"
)

func mulMod(a, b, m uint64) uint64 {
	hi, lo := bits.Mul64(a, b)
	_, rem := bits.Div64(hi, lo, m)
	return rem
}

func power(base, exp, mod uint64) uint64 {
	res := uint64(1)
	base %= mod
	for exp > 0 {
		if exp%2 == 1 {
			res = mulMod(res, base, mod)
		}
		base = mulMod(base, base, mod)
		exp /= 2
	}
	return res
}

func isPrime(n uint64) bool {
	if n < 2 {
		return false
	}
	if n == 2 || n == 3 {
		return true
	}
	if n%2 == 0 {
		return false
	}
	d := n - 1
	s := 0
	for d%2 == 0 {
		d /= 2
		s++
	}
	bases := []uint64{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}
	for _, a := range bases {
		if n <= a {
			break
		}
		x := power(a, d, n)
		if x == 1 || x == n-1 {
			continue
		}
		composite := true
		for r := 1; r < s; r++ {
			x = mulMod(x, x, n)
			if x == n-1 {
				composite = false
				break
			}
		}
		if composite {
			return false
		}
	}
	return true
}

func absDiff(a, b uint64) uint64 {
	if a > b {
		return a - b
	}
	return b - a
}

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

func pollardRho(n uint64, c uint64) uint64 {
	x := uint64(2)
	y := uint64(2)
	d := uint64(1)
	for d == 1 {
		x = (mulMod(x, x, n) + c) % n
		y = (mulMod(y, y, n) + c) % n
		y = (mulMod(y, y, n) + c) % n
		d = gcd(absDiff(x, y), n)
		if d == n {
			return 0
		}
	}
	return d
}

var smallPrimes = []uint64{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

func getFactor(n uint64) uint64 {
	for _, p := range smallPrimes {
		if n%p == 0 {
			return p
		}
	}
	if isPrime(n) {
		return n
	}
	c := uint64(1)
	for {
		d := pollardRho(n, c)
		if d != 0 && d != n {
			return d
		}
		c++
	}
}

func getPrimeFactors(n uint64) []uint64 {
	var factors []uint64
	var factorize func(n uint64)
	factorize = func(n uint64) {
		if n == 1 {
			return
		}
		if isPrime(n) {
			factors = append(factors, n)
			return
		}
		d := getFactor(n)
		factorize(d)
		factorize(n / d)
	}
	factorize(n)
	unique := make(map[uint64]bool)
	var res []uint64
	for _, f := range factors {
		if !unique[f] {
			unique[f] = true
			res = append(res, f)
		}
	}
	return res
}

type Element struct {
	val     uint64
	primes  []uint64
	isPower bool
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())

	if !scanner.Scan() {
		return
	}
	k, _ := strconv.Atoi(scanner.Text())

	x := make([]uint64, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		x[i], _ = strconv.ParseUint(scanner.Text(), 10, 64)
	}

	elements := make([]Element, n)
	powerPool := make(map[uint64][]uint64)

	for i := 0; i < n; i++ {
		primes := getPrimeFactors(x[i])
		isPower := len(primes) == 1
		elements[i] = Element{val: x[i], primes: primes, isPower: isPower}
		if isPower {
			p := primes[0]
			powerPool[p] = append(powerPool[p], x[i])
		}
	}

	validPrimes := []uint64{}
	isValid := make(map[uint64]bool)
	for p, pool := range powerPool {
		if len(pool) >= 2 {
			validPrimes = append(validPrimes, p)
			isValid[p] = true
		}
	}

	composites := []uint64{}
	compositePrimes := make(map[uint64][]uint64)
	for _, el := range elements {
		if el.isPower {
			continue
		}
		allValid := true
		for _, p := range el.primes {
			if !isValid[p] {
				allValid = false
				break
			}
		}
		if allValid {
			composites = append(composites, el.val)
			compositePrimes[el.val] = el.primes
		}
	}

	m := k / 2
	var chosen []uint64

	if k%2 == 0 {
		if len(validPrimes) >= m {
			for i := 0; i < m; i++ {
				p := validPrimes[i]
				chosen = append(chosen, powerPool[p][0], powerPool[p][1])
			}
		} else {
			for _, p := range validPrimes {
				chosen = append(chosen, powerPool[p][0], powerPool[p][1])
			}
			pool := []uint64{}
			for _, p := range validPrimes {
				if len(powerPool[p]) > 2 {
					pool = append(pool, powerPool[p][2:]...)
				}
			}
			pool = append(pool, composites...)

			rem := k - len(chosen)
			if len(pool) >= rem {
				chosen = append(chosen, pool[:rem]...)
			}
		}
	} else {
		if len(validPrimes) <= m {
			for _, p := range validPrimes {
				chosen = append(chosen, powerPool[p][0], powerPool[p][1])
			}
			pool := []uint64{}
			for _, p := range validPrimes {
				if len(powerPool[p]) > 2 {
					pool = append(pool, powerPool[p][2:]...)
				}
			}
			pool = append(pool, composites...)

			rem := k - len(chosen)
			if len(pool) >= rem {
				chosen = append(chosen, pool[:rem]...)
			}
		} else {
			var p3 uint64 = 0
			for _, p := range validPrimes {
				if len(powerPool[p]) >= 3 {
					p3 = p
					break
				}
			}
			if p3 != 0 {
				chosen = append(chosen, powerPool[p3][0], powerPool[p3][1], powerPool[p3][2])
				count := 0
				for _, p := range validPrimes {
					if p == p3 {
						continue
					}
					if count < m-1 {
						chosen = append(chosen, powerPool[p][0], powerPool[p][1])
						count++
					}
				}
			} else {
				var bestC uint64 = 0
				for _, c := range composites {
					if len(compositePrimes[c]) <= m {
						bestC = c
						break
					}
				}
				if bestC != 0 {
					chosen = append(chosen, bestC)
					cPrimes := compositePrimes[bestC]
					inC := make(map[uint64]bool)
					for _, p := range cPrimes {
						chosen = append(chosen, powerPool[p][0], powerPool[p][1])
						inC[p] = true
					}
					count := len(cPrimes)
					for _, p := range validPrimes {
						if inC[p] {
							continue
						}
						if count < m {
							chosen = append(chosen, powerPool[p][0], powerPool[p][1])
							count++
						}
					}
				}
			}
		}
	}

	if len(chosen) == k {
		for i, v := range chosen {
			if i > 0 {
				fmt.Print(" ")
			}
			fmt.Print(v)
		}
		fmt.Println()
	} else {
		fmt.Println(0)
	}
}
```