Largest Divisible Subset

Given an array of distinct positive integers, find the largest subset \(S\) such that for every pair of elements \(a, b \in S\) with \(a \le b\), the divisibility condition holds, i.e., \(b \mod a = 0\).

If there are multiple valid solutions, you may output any of them. The subset should be printed in increasing order.

Example: For the input array [1, 2, 4, 8], the entire array is a valid largest divisible subset since:

• 2 % 1 = 0
• 4 % 1 = 0, 4 % 2 = 0
• 8 % 1 = 0, 8 % 2 = 0, 8 % 4 = 0

Use the formula \(b \mod a = 0\) where applicable.

inputFormat

The input is read from standard input (stdin). The format is as follows:

1. The first line contains an integer \(n\) representing the number of elements.
2. The second line contains \(n\) space-separated integers.

outputFormat

Output the largest divisible subset (one of them if multiple exist) as a list of space-separated integers in increasing order on a single line. The output should be written to standard output (stdout).

4
1 2 4 8

1 2 4 8