题目描述

给定 $n$ 个点以及它们的权值 $a[1 \ldots n]$。如果 $i \leq j$ 且 $\operatorname{gcd}(a[i], a[j])>1$ ，那么从点 $i$ 可以到达点 $j$。请注意：

• 点 $i$ 能到达自身；
• $\operatorname{gcd}(0,0)=0$。

现在给出 $q$ 个询问 $(x, y)$，你需要判断从 $a[x]$ 是否可以到达 $a[y]$。

输入格式

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

第二行包含 $n$ 个整数 $a[1 \ldots n]$。

接下来 $q$ 行，每行包含两个整数 $(x, y)$，代表一组询问。

输出格式

输出 $q$ 行。每行输出"Shi"或者"Fou"，代表询问的答案。

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

Fou
Shi
Fou
Shi

样例解释 1

在第一个示例中，

• 第一个询问，从 $a[1]$ 到 $a[3]$，由于 $\operatorname{gcd}(1, 0) = 1$，所以不能到达，输出 "Fou"。
• 第二个询问，从 $a[2]$ 到 $a[4]$，可以通过 $a[3]$ 到达，所以输出 "Shi"。
• 第三个询问，从 $a[1]$ 到 $a[4]$，由于没有点的 gcd 值大于 1，所以不能到达，输出 "Fou"。
• 第四个询问，从 $a[1]$ 到 $a[1]$，可以到达自身，所以输出 "Shi"。

数据规模与约定

对于 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$

大样例

大样例下载