火星是一种不寻常蜘蛛的家园——二元蜘蛛。
目前,火星科学家正在观察一群 $$$n$$$ 蜘蛛,其中第 $$$i$$$ 拥有 $$$a_i$$$ 腿。
有些蜘蛛彼此是朋友。也就是说,如果 $$$\gcd(a_i, a_j) \ne 1$$$, i,则第 $$$i$$$ 和第 $$$j$$$ 蜘蛛是朋友。 即,存在某个整数 $$$k \ge 2$$$ 使得 $$$a_i$$$ 和 $$$a_j$$$ 同时除以 $$$k$$$ 而没有余数。这里 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
科学家发现蜘蛛可以发送信息。如果两个蜘蛛是朋友,那么它们可以在一秒钟内直接传输消息。否则,蜘蛛必须将消息传递给他的朋友,而他的朋友又必须将消息传递给他的朋友,依此类推,直到消息到达收件人。
让我们看一个例子。
假设一个有八条腿的蜘蛛想要向一个有 $$$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$$$) - 消息应遵循的蜘蛛的 ID,按照从发送者到接收者的顺序。
如果消息有多个最佳路由,则输出其中任意一个。
示例
输入 #1
7 2 14 9 6 8 15 11 5 6
输出 #1
3 5 4 6
输入 #2
7 2 14 9 6 8 15 11 5 7
输出 #2
-1
输入 #3
7 2 14 9 6 8 15 11 5 5
输出 #3
1 5
注意
第一个示例如上所示。它表明,从第 $$$5$$$ 个蜘蛛(有 8 条腿)到第 $$$6$$$ 条蜘蛛(有 $$$15$$$ 条腿)的消息最适合通过第 $$$4$$$ 条蜘蛛(有 6 条腿)。
在第二个例子中,蜘蛛号$$$7$$$(有$$$11$$$腿)不是任何人的朋友,因此不可能向他发送消息。