公约数神庙

题目信息

时间限制: 1s

空间限制: 128M

输入文件: gcd.in

输出文件: gcd.out

题目描述

当大地陷入了混乱和分裂，一位智者带来了一本神秘的古老书籍。这本书上写着关于 $n$ 个古老神庙的秘密，每座神庙都藏有珍贵的宝物。这些神庙被分布在各种不同的地方，被认为是人类文明的遗产。

第 $i$ 座神庙有一个独特的权值 $a[i]$，代表着其中蕴含的智慧和力量。这些神庙之间有着一种神秘的联系：若 $i\leq j$ 且 $gcd(a[i], a[j]) > 1$，那么你可以从神庙 $i$ 走到神庙 $j$。额外约定：

• 神庙 $i$ 能走到神庙 $i$
• $gcd(0, 0)=0$

现在，你面临 $q$ 个询问 $(x, y)$，你希望知道是否存在一条路径可以从神庙 $x$ 走到神庙 $y$，从而传递它们的智慧和力量。你的探险将成为人们口中的传奇，这个世界将因你的行动而改变！

输入格式

第一行包含两个整数 $n, q$，表示神庙的数量和询问的数量。

第二行包含 $n$ 个整数 $a[1], a[2], \cdots, a[n]$，表示每座神庙的权值。

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

输出格式

对于每个询问，输出一行，如果存在一条路径可以从神庙 $x$ 走到神庙 $y$，输出 Shi，否则输出 Fou。

样例

样例输入1

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

样例输出1

Fou
Shi
Fou
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$