← 返回题目列表

Codeforces · 632/D

D. 最长子序列

中文机器翻译题面 查看原题

给定数组 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