题目背景

星港中有 $n$ 座信标。第 $i$ 座信标有一个编号 $a_i$，并会在第 $b_i$ 天启封。

两座已经启封的信标若编号有大于 $1$ 的公因数，就可以直接传讯。传讯可以经过若干座已经启封的中继信标。

现在有 $q$ 次询问。每次给定两座信标 $s,t$，你需要求出最早在哪一天，信号可以从 $s$ 传到 $t$。

题目描述

在第 $T$ 天，所有满足 $b_i\le T$ 的信标可用。

若两座可用信标 $i,j$ 满足 $\gcd(a_i,a_j)>1$，则它们之间可以直接传讯。

对于每个询问 $(s,t)$，输出最小的 $T$，使得第 $T$ 天时 $s$ 能通过若干次直接传讯到达 $t$。如果无论等到哪一天都无法传到，输出 $-1$。

特别地，若 $s=t$，答案定义为 $b_s$。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

第三行包含 $n$ 个整数 $b_1,b_2,\dots,b_n$。

接下来 $q$ 行，每行包含两个整数 $s,t$，表示一次询问。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 个询问的答案。

样例

输入

6 6
6 10 15 7 14 1
4 9 6 2 8 5
1 3
4 2
4 3
6 1
2 2
4 1

输出

6
9
8
-1
9
8

样例解释

第 $1$ 座和第 $3$ 座信标编号分别为 $6$ 与 $15$，有公共质因子 $3$，两者都启封后即可直接传讯，最早是第 $6$ 天。

第 $4$ 座可以经过第 $5$ 座、第 $1$ 座到达第 $3$ 座，对应编号 $7\to14\to6\to15$，这条链最晚启封的信标是第 $5$ 座，启封日为 $8$，因此答案为 $8$。

第 $6$ 座编号为 $1$，不能通过公共质因子连向其他信标。

数据范围

对于所有测试数据：

• $1\le n,q\le 3\cdot 10^5$；
• $1\le a_i\le 3\cdot 10^5$；
• $1\le b_i\le 10^9$；
• $1\le s,t\le n$。