D. Longest Subsequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given array a with n elements and the number m. Consider some subsequence of a and the value of least common multiple (LCM) of its elements. Denote LCM as l. Find any longest subsequence of a with the value l ≤ m.A subsequence of a is an array we can get by erasing some elements of a. It is allowed to erase zero or all elements.The LCM of an empty array equals 1.InputThe first line contains two integers n and m (1 ≤ n, m ≤ 106) — the size of the array a and the parameter from the problem statement.The second line contains n integers ai (1 ≤ ai ≤ 109) — the elements of a.OutputIn the first line print two integers l and kmax (1 ≤ l ≤ m, 0 ≤ kmax ≤ n) — the value of LCM and the number of elements in optimal subsequence.In the second line print kmax integers — the positions of the elements from the optimal subsequence in the ascending order.Note that you can find and print any subsequence with the maximum length.ExamplesInput7 86 2 9 2 7 2 3Output6 51 2 4 6 7Input6 42 2 2 3 3 3Output2 31 2 3
Input7 86 2 9 2 7 2 3
Output6 51 2 4 6 7
['brute force', 'math', 'number theory', '*2100']