C. Совершенные кратные Канадэ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мы врезали эти воспоминания в себя... Как бы трудно это ни было, это жизни, которые мы прожили!
— Angel Beats!

В загробной школе Канадэ изучает необычную числовую игру.

Она даёт вам два целых числа $$$n$$$ и $$$k$$$, а также массив $$$a$$$, состоящий из $$$n$$$ целых чисел, где $$$1 \le a_i \le k$$$.

Для множества целых чисел $$$B = \{b_1, b_2, \ldots, b_m\}$$$, где $$$1\le b_i\le k$$$, мы называем его полным тогда и только тогда, когда выполняются оба следующих условия:

  • Для каждого $$$1\le i\le n$$$ хотя бы один делитель $$$a_i$$$ содержится в $$$B$$$;
  • Для каждого $$$1\le j\le m$$$ все положительные делящиеся на $$$b_j$$$ числа, которые меньше или равны $$$k$$$, появляются в массиве $$$a$$$ хотя бы один раз.

Вам нужно найти полное множество $$$B$$$ минимально возможного размера или определить, что такое множество не существует.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le k\le 10^9$$$) — длина массива $$$a$$$ и верхняя граница элементов массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le k$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных:

  • Если не существует полного множества $$$B$$$, выведите одно целое число $$$-1$$$ в единственной строке вывода.
  • В противном случае:
    • Сначала выведите одно целое число $$$m$$$ ($$$1\le m\le n$$$) в первой строке вывода — размер $$$B$$$. Обратите внимание, что вам нужно минимизировать размер $$$B$$$.
    • Затем выведите $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le k$$$) во второй строке — множество, которое вы построили.

Если существует несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
4
4 6
3 2 4 6
5 5
1 2 3 4 5
3 6
2 3 6
1 2
2
Выходные данные
2
2 3 
1
1 
-1
1
2
Примечание

В первом наборе входных данных $$$B=\{2,3\}$$$ подходит. Для $$$b=2$$$ все кратные $$$\{2,4,6\}$$$ (до $$$k=6$$$) появляются в $$$a$$$; для $$$b=3$$$ кратные $$$\{3,6\}$$$ появляются. Каждое $$$a_i$$$ делится на $$$2$$$ или $$$3$$$. Ни одно $$$b$$$ размера 1 не может удовлетворить обоим условиям, поэтому $$$m=2$$$ минимально.

Во втором наборе входных данных $$$B=\{1\}$$$ удовлетворяет обоим правилам, так как каждое число делится на $$$1$$$, и все кратные $$$1$$$ до $$$k$$$ появляются.