Вам задан массив a из n элементов и число m. Рассмотрим некоторую подпоследовательность a и значение наименьшего общего кратного (НОК) её элементов. Обозначим этот НОК буквой l. Найдите самую длинную подпоследовательность массива a со значением l ≤ m.
Подпоследовательностью массива a называется массив, который получается из a удалением некоторых элементов. Разрешено удалять ноль или все элементы массива.
НОК пустого массива равен 1.
Выходные данные
В первой строке выведите два целых числа l и kmax (1 ≤ l ≤ m, 0 ≤ kmax ≤ n) — значение НОК и количество элементов в оптимальной подпоследовательности.
Во второй строке выведите kmax целых чисел — позиции элементов в исходной последовательности, в возрастающем порядке.
Заметим, что вы можете найти и вывести любую подпоследовательность с наибольшей длиной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 8
6 2 9 2 7 2 3
|
6 5
1 2 4 6 7
|
|
2
|
6 4
2 2 2 3 3 3
|
2 3
1 2 3
|