题目描述

面条老师画了一张图。在这个图中包含 $n$ 个点，每个点拥有一个权值 $a_i$。

这个图非常特别，遵循以下特征：

1. 每个点都有一条连向自己的边。
2. 对于 $i,j(i < j)$ 两个节点，如果 $gcd(a_i,a_j) > 1$，那么存在一条 $i$ 连向 $j$ 的单向边。
3. 由于图中存在权值为零的点，这里规定 $gcd(0,0)=0,gcd(i,0)=i$。

面条老师接下来向你发起挑战：共计有$q$次查询，每次查询会问你能否从点$x$出发到达点$y$。对于每次查询回答 YES和NO。

输入格式

输入第一行包含两个整数 $n,q$，含义如题。

输入第二行包含 $n$ 个整数 $a_i$，分别表示每个点的权值。

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

输出格式

对于每次询问输出一行，如果点 $x$ 能到达点 $y$ 则输出 YES 否则输出 NO。

5 4
1 3 0 2 1
1 3
2 4
1 4
1 1

NO
YES
NO
YES

样例解释

数据规模与约定

对于 $40\%$ 的数据，$n, q \leq 1000,0 \leq a_i \leq 10$

对于 $80\%$ 的数据，$n, q \leq 1000,0 \leq a_i \leq 500$

对于 $100\%$ 的数据，$n, q \leq 10^5, 0 \leq a_i \leq 1000, x \leq y$

大样例

大样例下载