Longest Divisible Subsequence

You are given a sequence of integers and an integer (k). Your task is to find the longest subsequence from the given list such that each element of the subsequence is divisible by (k). If there are multiple subsequences of the same maximum length, you must return the lexicographically smallest one (i.e. the subsequence with its elements in increasing order).

For example, if the input is n = 5, the sequence is [7, 14, 21, 28, 35] and k = 7, then the correct output is 7 14 21 28 35.

inputFormat

The input is given from standard input (stdin) as follows:

• The first line contains an integer \(n\) which indicates the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the sequence.
• The third line contains an integer \(k\).

outputFormat

Print a single line to standard output (stdout) containing the elements of the longest divisible subsequence separated by a single space. If no element in the sequence is divisible by (k), print an empty line.## sample

5
7 14 21 28 35
7

7 14 21 28 35