Question
The Council of Divisible Numbers
In the Land of Integers, there exists a set of n distinct positive numbers, given through an array called nums.
The King wishes to form the largest possible council from these numbers such that every two members of the council live in harmony with each other.
Two numbers a and b are said to be in harmony if one divides the other, that is:
-
a % b == 0, or -
b % a == 0.
Your task is to find and print the largest harmonious subset of numbers from nums that satisfies this rule.
If there are multiple possible councils, you may return any one of them.
Input
The first line of the input contains a single integer n, representing the size of the array nums.
The second line of the input contains n space separated integers representing elements of the array nums.
The second line of the input contains n space separated integers representing elements of the array nums.
Output
Print the largest subset that satisfies the given conditions.
Example
Sample Input
3
1 2 3
Sample Output
1 2
Explanation
[1, 2] and [1, 3] are both valid subsets.
3
1 2 3
Sample Output
1 2
Explanation
[1, 2] and [1, 3] are both valid subsets.