给定数组 a,其中包含 n 个元素和数字 m。考虑 a 的某个子序列及其元素的最小公倍数 (LCM) 值。将 LCM 表示为 l。找到 a 的任意最长子序列,其值 l ≤ m。
a的子序列是我们可以通过删除a的一些元素得到的数组。允许删除零个或所有元素。
空数组的 LCM 等于 1。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 106) — 数组 a 的大小和问题陈述中的参数。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — a 的元素。
输出
在第一行中打印两个整数 l 和 kmax (1 ≤ l ≤ m, 0 ≤ kmax ≤ n) — LCM 的值和最优子序列中的元素数量。
在第二行中打印 kmax 整数 — 最优子序列中元素的位置(按升序排列)。
请注意,您可以查找并打印任何具有最大长度的子序列。
示例
输入 #1
7 8 6 2 9 2 7 2 3
输出 #1
6 5 1 2 4 6 7
输入 #2
6 4 2 2 2 3 3 3
输出 #2
2 3 1 2 3