Райан прилагает последние усилия, чтобы завоевать сердце Рейхане, утверждая, что он сильнее Райанех (то есть компьютера на персидском). Чтобы проверить это, Рейхане обращается за помощью к Хорезми. Хорезми объясняет, что множество является целочисленно линейно независимым, если ни один элемент в наборе не может быть получен как целочисленная линейная комбинация остальных. Райану задается набор целых чисел, и он должен найти одно из максимально возможных целочисленных линейно независимых подмножеств.
Обратите внимание, что один элемент всегда является целочисленным линейно независимым подмножеством.
Целочисленная линейная комбинация чисел \(a_1, \ldots, a_k\) — это любая сумма вида \(c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k\) где \(c_1, c_2, \ldots, c_k\) — целые числа (которые могут быть нулевыми, положительными или отрицательными).
Выходные данные
В первой строке каждого набора входных данных выведите размер наибольшего целочисленного линейно независимого подмножества.
В следующей строке выведите одно такое подмножество. Если существует несколько ответов, выведите любой из них.
Примечание
В 1 наборе входных данных: \(\{4, 6\}\) — это целочисленное линейно независимое подмножество. Можно доказать, что не существует целочисленного линейно независимого подмножества, состоящего по крайней мере \(3\) из элементов.
Во 2 наборе входных данных: \(\{35, 21, 30\}\) — это целочисленное линейно независимое подмножество, поскольку никакая целочисленная линейная комбинация любых двух элементов не может создать третий. Не существует целочисленного линейно независимого подмножества, содержащего по крайней мере \(4\) элемента.
В 3 наборе входных данных: \(\{2, 3, 6\}\) не является целочисленным линейно независимым подмножеством, поскольку \(6\) может быть записано как \(6 \cdot 2 + (-2) \cdot 3\), что является целочисленной линейной комбинацией из \(\{2, 3\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
2 4 6 8 10
5
12 15 21 30 35
3
2 3 6
|
2
4 6
3
35 21 30
2
2 3
|