Toad Pimple 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。
如果 $$$x<y$$$ 并且存在一个整数数组 $$$p$$$ 使得 $$$x = p_1 < p_2 < \ldots < p_k=y$$$,并且 $$$a_{p_i}\, \&\, a_{p_{i+1}} >,我们说 $$$y$$$ 可以从 $$$x$$$ 到达0$$$ 对于所有整数 $$$i$$$ 使得 $$$1 \leq i < k$$$。
这里$$$\&$$$表示按位与运算。
给你 $$$q$$$ 索引对,检查每个索引的可达性。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 300\,000$$$, $$$1 \leq q \leq 300\,000$$$) - 数组中整数的数量以及需要回答的查询数量。
第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 300\,000$$$) — 给定数组。
接下来的 $$$q$$$ 行每行包含两个整数。其中第 $$$i$$$ 包含两个空格分隔的整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \leq x_i < y_i \leq n$$$)。您需要检查 $$$y_i$$$ 是否可以从 $$$x_i$$$ 到达。
输出
输出 $$$q$$$ 行。在其中的第 $$$i$$$ 中,如果 $$$y_i$$$ 可以从 $$$x_i$$$ 到达,则打印“Shi”,否则打印“Fou”。
示例
输入 #1
5 3 1 3 0 2 1 1 3 2 4 1 4
输出 #1
Fou Shi Shi
注意
在第一个示例中,$$$a_3 = 0$$$。你无法达到它,因为与它的 AND 总是零。 $$$a_2\, \&\, a_4 > 0$$$,因此 $$$4$$$ 可以从 $$$2$$$ 到达,并且从 $$$1$$$ 到 $$$4$$$ 可以使用 $$$p = [1, 2, 4]$$$。