← 返回题目列表

Codeforces · 1168/C

C. 和可达性

中文机器翻译题面 查看原题

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]$$$。