На Марсе обитает необычный вид пауков — двоичные пауки.
Прямо сейчас марсианские ученые наблюдают за колонией из \(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\)-му пауку. У исследователей есть гипотеза, что пауки всегда передают сообщения оптимально. По этой причине ученым потребуется программа, которая смогла бы вычислить минимальное время передачи сообщения, а также вывести один из оптимальных маршрутов.
Выходные данные
Если передать сообщение между заданной парой пауков невозможно, выведите \(-1\).
Иначе в первой строке выходных данных выведите целое число \(t\) (\(t \ge 1\)) — количество пауков, которые участвуют в передаче сообщения (т. е. минимальное время доставки сообщения в секундах плюс один). Во второй строке выведите \(t\) различных целых чисел \(b_1, b_2, \ldots, b_t\) (\(1 \le b_i \le n\)) — номера пауков, через которых должно следовать сообщение, в порядке его следования от отправителя к получателю.
Если вариантов построения оптимального маршрута для сообщения несколько, то выведите любой из них.
Примечание
Первый пример разобран выше. В нем видно, что сообщение от паука номер \(5\) (с восемью лапками) к пауку номер \(6\) (с \(15\)-ю лапками) оптимально передать через паука номер \(4\) (с шестью лапками).
Во втором примере паук номер \(7\) (с \(11\) лапками) ни с кем не дружит, поэтому ему невозможно передать сообщение.