D. Дружелюбные пауки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На Марсе обитает необычный вид пауков — двоичные пауки.

Прямо сейчас марсианские ученые наблюдают за колонией из $$$n$$$ пауков, $$$i$$$-й из которых имеет $$$a_i$$$ лапок.

Некоторые пауки дружат между собой. А именно, $$$i$$$-й и $$$j$$$-й пауки являются друзьями, если $$$\gcd(a_i, a_j) \ne 1$$$, т. е. существует некоторое число $$$k \ge 2$$$ такое, что $$$a_i$$$ и $$$a_j$$$ одновременно делятся на $$$k$$$ без остатка. Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Ученые обнаружили, что пауки могут передавать сообщения. Если два паука являются друзьями, то тогда они могут передать сообщение напрямую за одну секунду. Иначе паук должен передать сообщение своему другу, тот, в свою очередь, должен передать сообщение своему другу, и так далее, пока сообщение не дойдет до адресата.

Рассмотрим пример.

Пусть паук с восемью лапками хочет передать сообщение пауку с $$$15$$$-ю лапками. Напрямую он этого сделать не может, потому что $$$\gcd(8, 15) = 1$$$. Зато он может передать сообщение через паука с шестью лапками, поскольку $$$\gcd(8, 6) = 2$$$ и $$$\gcd(6, 15) = 3$$$. Таким образом, сообщение дойдет за две секунды.

Прямо сейчас ученые наблюдают, как $$$s$$$-й паук хочет передать сообщение $$$t$$$-му пауку. У исследователей есть гипотеза, что пауки всегда передают сообщения оптимально. По этой причине ученым потребуется программа, которая смогла бы вычислить минимальное время передачи сообщения, а также вывести один из оптимальных маршрутов.

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

В первой строке входных данных находится целое число $$$n$$$ ($$$2 \le n \le 3\cdot10^5$$$) — количество пауков в колонии.

Во второй строке входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 3\cdot10^5$$$) — количество лапок у пауков.

В третьей строке входных данных находится два целых числа $$$s$$$ и $$$t$$$ ($$$1 \le s, t \le n$$$) — пауки, между которыми необходимо передать сообщение.

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

Если передать сообщение между заданной парой пауков невозможно, выведите $$$-1$$$.

Иначе в первой строке выходных данных выведите целое число $$$t$$$ ($$$t \ge 1$$$) — количество пауков, которые участвуют в передаче сообщения (т. е. минимальное время доставки сообщения в секундах плюс один). Во второй строке выведите $$$t$$$ различных целых чисел $$$b_1, b_2, \ldots, b_t$$$ ($$$1 \le b_i \le n$$$) — номера пауков, через которых должно следовать сообщение, в порядке его следования от отправителя к получателю.

Если вариантов построения оптимального маршрута для сообщения несколько, то выведите любой из них.

Примеры
Входные данные
7
2 14 9 6 8 15 11
5 6
Выходные данные
3
5 4 6
Входные данные
7
2 14 9 6 8 15 11
5 7
Выходные данные
-1
Входные данные
7
2 14 9 6 8 15 11
5 5
Выходные данные
1
5
Примечание

Первый пример разобран выше. В нем видно, что сообщение от паука номер $$$5$$$ (с восемью лапками) к пауку номер $$$6$$$ (с $$$15$$$-ю лапками) оптимально передать через паука номер $$$4$$$ (с шестью лапками).

Во втором примере паук номер $$$7$$$ (с $$$11$$$ лапками) ни с кем не дружит, поэтому ему невозможно передать сообщение.